JOI Open Contest

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, \dots, 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, \dots, f_N~, we must have ~|f_1 - f_2| + |f_2 - f_3| + \dots + |f_{N-1} - f_N| \le L~. Here, ~|x|~ is the absolute value of ~x~.

How many permutations of buildings satisfy the above conditions?

Task

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 ~1\,000\,000\,007~.

Input Specification

Read the following data from the standard input.

• The first line contains two space separated integers, ~N~, ~L~. 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, \dots, A_N~. This means the height of the ~i~-th building ~(1 \le i \le N)~ is ~A_i~.

Output Specification

The output consists of one line. It contains an integer, the remainder of division of the number of permutations of buildings satisfying the condition by ~1\,000\,000\,007~.

Constraints

All input data satisfy the following conditions.

• ~1 \le N \le 100~.
• ~1 \le L \le 1\,000~.
• ~1 \le A_i \le 1\,000~.
• ~A_i \ne A_j~ ~(1 \le i < j \le N)~.

Subtasks

Subtask 1 [5 points]

• ~N \le 8~.

Subtask 2 [15 points]

The following conditions are satisfied.

• ~N \le 14~.
• ~L \le 100~.

Subtask 3 [80 points]

There are no additional constraints.

Sample Input 1

4 10
3 6 2 9

Sample Output 1

6

Explanation for Sample Output 1

There are 24 permutations in total. Among them, there are 6 permutations for which the sums of the absolute values of the differences of the heights of two adjacent builds are less than or equal to 10.

• If ~f_1 = 2~, ~f_2 = 3~, ~f_3 = 6~, ~f_4 = 9~, we have ~|2 - 3| + |3 - 6| + |6 - 9| = 7~.
• If ~f_1 = 2~, ~f_3 = 3~, ~f_3 = 9~, ~f_4 = 6~, we have ~|2 - 3| + |3 - 9| + |9 - 6| = 10~.
• If ~f_1 = 3~, ~f_2 = 2~, ~f_3 = 6~, ~f_4 = 9~, we have ~|3 - 2| + |2 - 6| + |6 - 9| = 8~.
• If ~f_1 = 6~, ~f_2 = 9~, ~f_3 = 3~, ~f_4 = 2~, we have ~|6 - 9| + |9 - 3| + |3 - 2| = 10~.
• If ~f_1 = 9~, ~f_2 = 6~, ~f_3 = 2~, ~f_4 = 3~, we have ~|9 - 6| + |6 - 2| + |2 - 3| = 8~.
• If ~f_1 = 9~, ~f_2 = 6~, ~f_3 = 3~, ~f_4 = 2~, we have ~|9 - 6| + |6 - 3| + |3 - 2| = 7~.

Sample Input 2

8 35
3 7 1 5 10 2 11 6

Sample Output 2

31384