Problem Description

Given \( n \) magnets and \( l \) slots, where the distance between adjacent slots is 1, each slot can hold one magnet. All \( n \) magnets must be placed. Each magnet can attract other magnets within a distance less than \( r_i \).

Find the total number of arrangements where no magnets attract each other, modulo \( 10^9 + 7 \).

Input Format

The first line contains two positive integers \( n \) and \( l \), representing the number of magnets and slots, respectively.

The second line contains \( n \) integers \( r_i \).

Output Format

Output the total number of arrangements modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

1 10
10

Sample Output #1

10

Sample Input #2

4 4
1 1 1 1

Sample Output #2

24

Sample Input #3

3 4
1 2 1

Sample Output #3

4

Notes

Sample 2 Explanation: All permutations of the four magnets are valid.

Sample 3 Explanation:

Using \(\texttt{1, 2, 3}\) to denote magnets and \(\texttt{\_}\) to denote slots, the valid arrangements are: \(\texttt{13\_2}\), \(\texttt{31\_2}\), \(\texttt{2\_13}\), and \(\texttt{2\_31}\).

Data Range and Constraints:

This problem uses subtask-based testing.

• Subtask 1 (10 pts): \( r_1 = r_2 = \cdots = r_n \).
• Subtask 2 (20 pts): \( 1 \le n \le 10 \).
• Subtask 3 (30 pts): \( 1 \le n \le 30 \), \( n \le l \le 300 \).
• Subtask 4 (50 pts): No special restrictions.

For 100% of the data, \( 1 \le n \le 50 \), \( n \le l \le 10000 \), \( 1 \le r_i \le l \).

Translated from COCI 2021-2022 CONTEST #2 Task 4 Magneti.

This problem's score is set according to the original COCI, with a maximum of 110 points.

见题面 Input 部分

见题面 Output 部分