P7967 [COCI 2021/2022 #2] Magnets

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$.

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 the total number of valid ways modulo $10^9+7$.

**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](https://hsin.hr/coci/) [CONTEST #2](https://hsin.hr/coci/contest2_tasks.pdf) _Task 4 Magneti_.** **The score settings follow the original COCI problem, with a full score of $110$.** Translated by ChatGPT 5