Skyscraper#11818

Skyscraper

1 second

128 megabytes

Very hard

The International Olympiad in Informatics will be held in Tsukuba City, Japan. In order to prepare for IOI, we are planning to construct skyscraper buildings in the main street of Tsukuba City. Since we want to create a new sightseeing spot, the buildings have to satisfy the following conditions.

We are planning to construct $n$ buildings along a straight line in the main street. The heights of them are $a_{1}, a_{2}, a_{3}, ..., a_{n}$ a_1, a_2, a_3, ..., a_n. They are different from each other. Since the order of $n$ buildings are not yet decided, we can permute their heights if necessary. We will decorate them for IOI. Due to the constraints of materials used for decoration, the sum of the absolute values of the differences of the heights of two adjacent buildings must be less than or equal to $L$ . In other words, if the heights of the buildings from one side of the main street are $f_{1}, f_{2}, f_{3}, ..., f_{n}$ f_1, f_2, f_3, ..., f_n, we must have

∣ f_{1} - f_{2} ∣ + ∣ f_{2} - f_{3} ∣ + ... + ∣ f_{n - 1} - f_{n} ∣ \leq L

|f_1 - f_2| + |f_2 - f_3| + ... + |f_{n-1} - f_n| \le L

Here, $∣ x ∣$ is the absolute value of $x$ .

How many permutations of buildings satisfy the above condition?

Given the number $n$ of buildings, their heights, and the upper limit $L$ of the sum of the absolute values of the differences of the heights of two adjacent buildings, write a program which calculates the number of permutations of buildings satisfying the condition. Since this number can be too big, output the remainder of division of it by $1000000007$ .

Input

Read the following data from the standard input.

The first line of input contains two space separated integers $n$ and $L$ $(1 \leq n \leq 100, 1 \leq L \leq 1000)$ (1 \le n \le 100, 1 \le L \le 1000). This means the number of buildings is $n$ , and the upper limit of the sum of the absolute values of the differences of the heights of two adjacent buildings is $L$ .
The second line contains $n$ space separated integers $a_{1}, a_{2}, a_{3}, ..., a_{n}$ a_1, a_2, a_3, ..., a_n $(1 \leq a_{i} \leq 1000$ (1 \le a_i \le 1000 $(1 \leq i \leq n)$ (1 \le i \le n), $a_{i} \neq = a_{j}$ a_i \ne a_j $(1 \leq i < j \leq n))$ (1 \le i < j \le n)). This means the height of the $i$ -th building $(1 \leq i \leq n)$ (1 \le i \le n) is $a_{i}$ a_i.

Output

Print a single integer — the number of permutations of the buildings that satisfy the condition, modulo $1000000007$ .

Examples

Example 1

Example 2

Note

Subtask 1 [5 points]: $n \leq 8$ n \le 8.

Subtask 2 [15 points]: $n \leq 14, L \leq 100$ n \le 14, L \le 100.

Subtask 3 [80 points]: There are no additional constraints.