시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 77 | 43 | 36 | 65.455% |
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 A1, A2, A3, . . . , AN. 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 f1, f2, f3, . . . , fN, we must have |f1 − f2| + |f2 − f3| + . . . + |fN−1 − fN| ≤ 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 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.
There are no additional constraints.
4 10 3 6 2 9
6
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 heigts of two adjacent buildings are less than or equal to 10.
8 35 3 7 1 5 10 2 11 6
31384