16781번 - Skyscraper 서브태스크다국어

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₁, A₂, A₃, . . . , 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 heigts 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₁, f₂, f₃, . . . , f_N, we must have |f₁ − f₂| + |f₂ − f₃| + . . . + |f_N−1 − f_N| ≤ 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 heigts 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.

Read the following data from the standard input.

• The first line of input 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 heigts of two adjacent buildings is L.
• The second line contains N space separated integers A₁, A₂, A₃, . . . , A_N. This means the height of the i-th building (1 ≤ i ≤ N) is A_i.

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.

All input data satisfy the following conditions.

• 1 ≤ N ≤ 100.
• 1 ≤ L ≤ 1 000.
• 1 ≤ A_i ≤ 1 000 (1 ≤ i ≤ N).
• A_i ≠ A_j (1 ≤ i < j ≤ N).

• N ≤ 8.

• N ≤ 14.
• L ≤ 100.

There are no additional constraints.