Problem Description

Niwango-kun purchased land represented by the half-open interval $ [0,X) $.

Niwango-kun decided to lay $ N $ sheets on this land. The sheets are numbered $1, 2, \ldots, N$ and are distinguishable. The sheet $ i $ can be laid to cover the interval $ [j, j + L_i) $ by choosing an integer $ j $ that satisfies $0 \leq j \leq X - L_i$.

Find the number of ways to lay the sheets such that there are no uncovered coordinates in $ [0,X) $, modulo $ 10^9+7 $. Two ways of laying the sheets are considered different if there exists an integer $i (1 \leq i \leq N)$ such that the region covered by sheet $ i $ is different.

Input Format

The input is given from the standard input in the following format:

$ N $ $ X $ $ L_1 $ $ L_2 $ $\ldots$ $ L_N $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3 3
1 1 2

Sample Output #1

10

Sample Input #2

18 477
324 31 27 227 9 21 41 29 50 34 2 362 92 11 13 17 183 119

Sample Output #2

134796357

Notes/Hints

Constraints

• $1 \leq N \leq 100$
• $1 \leq L_i \leq X \leq 500$
• All values in the input are integers.

Sample Explanation 1

• Ignoring whether the entire interval is covered, the total number of ways to lay the sheets is $ 18 $.
• Among them, there are $ 4 $ ways where the interval $ [0,1) $ is not covered, and $ 4 $ ways where the interval $ [2,3) $ is not covered.
• The remaining ways can cover the entire interval $ [0,3) $, so the answer is $ 10 $.

Sample Explanation 2

• Find the total number of ways to lay the sheets modulo $ 10^9+7 $.

见题面 Input 部分

见题面 Output 部分