COCI '21 Contest 2 #4 Magneti

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Little Marko is bored of playing with shady cryptocurrencies such as Shiba Inu or XRC, which is why he decided to play with magnets. He has n different magnets and a board which has l available empty slots in a row, in which the magnets can be placed. Each pair of adjacent slots is exactly one centimeter apart. Each of the n magnets has a radius of activity that is equal to r_i. This means that it will attract all magnets that are located strictly less than r_i centimeters away (regardless of the radius of activity of the other magnet). It is possible that some magnets have the same radius of activity, but they are considered as different magnets.

Marko doesn't like it when the magnets attract each other, so he is interested in the number of ways to place the magnets on the board so that no magnet attracts any other. All of the magnets should be placed on the board, and each empty slot may contain at most one magnet. Two ways of placing the magnets are considered different if there is a magnet which is at a different position in the first way than in the second way. As the required number can be quite large, you should output it modulo 10^9 + 7.

Input Specification

The first line contains positive integers n and l, the number of magnets and the number of empty slots.

The second line contains n positive integers r_i (1 \le r_i \le l), the radii of activity of the n magnets.

Output Specification

Print the required number of ways to place the magnets on the board so that no magnet attracts any other, modulo 10^9 + 7.

Constraints

In every subtask, it holds that 1 \le n \le 50 and n \le l \le 10\,000.

SubtaskPointsConstraints
110r_1 = r_2 = \dots = r_n
2201 \le n \le 10
3301 \le n \le 30, n \le l \le 300
450No additional constraints.

Sample Input 1

1 10
10

Sample Output 1

10

Sample Input 2

4 4
1 1 1 1

Sample Output 2

24

Explanation for Sample Output 2

All permutations of the magnets are valid because no two magnets can attract each other.

Sample Input 3

3 4
1 2 1

Sample Output 3

4

Explanation for Sample Output 3

If we denote the magnets with 1, 2 and 3, and an empty slot with _, the possible arrangements of magnets are 13_2, 31_2, 2_13 and 2_31.


Comments

There are no comments at the moment.