Problem Description

You are given $n$ magnets and $l$ empty slots. The distance between adjacent slots is $1$, and each slot can hold one magnet. All $n$ magnets must be placed. Each magnet can attract other magnets whose distance is less than $r_i$.

Find the total number of ways to place the magnets so that no two magnets attract each other, modulo $10^9+7$.

Input Format

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

The second line contains $n$ integers $r_i$.

Output Format

Output the total number of valid ways modulo $10^9+7$.

1 10
10

10

4 4
1 1 1 1

24

3 4
1 2 1

4

Hint

Sample 2 Explanation: All permutations of the four magnets satisfy the requirements.

Sample 3 Explanation:

Use $\texttt{1,2,3}$ to represent magnets, and $\texttt \_$ to represent an empty slot. Then all valid arrangements are: $\texttt{13\_2}$, $\texttt{31\_2}$, $\texttt{2\_13}$, and $\texttt{2\_31}$.

Constraints

This problem uses bundled subtasks.

• 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 testdata, $1 \le n \le 50$, $n \le l \le 10000$, $1 \le r_i \le l$.

Hints and Notes

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

The score settings follow the original COCI problem, with a full score of $110$.

Translated by ChatGPT 5