[COCI2021-2022#2] Magneti

题目描述

给定 $n$ 个磁铁和 $l$ 个空位，其中相邻空位之间的距离为 $1$，每个空位可放置一个磁铁。所有 $n$ 个磁铁都必须被放置。每个磁铁可以吸引距离小于 $r_i$ 的其它磁铁。求所有磁铁互不吸引的方案总数对 $10^9+7$ 取模的结果。

输入输出格式

输入格式

第一行两个正整数 $n,l$，分别表示磁铁和空位数量。第二行 $n$ 个整数 $r_i$。

输出格式

输出方案总数对 $10^9+7$ 取模的结果。

输入输出样例

输入样例 #1

1 10
10

输出样例 #1

输入样例 #2

4 4
1 1 1 1

输出样例 #2

输入样例 #3

3 4
1 2 1

输出样例 #3

说明

**【样例 2 解释】** 四个磁铁的所有排列都符合题意。 **【样例 3 解释】** 用 $\texttt{1,2,3}$ 表示磁铁，$\texttt \_$ 表示空位，则所有方案为：$\texttt{13\_2}$、$\texttt{31\_2}$、$\texttt{2\_13}$ 和 $\texttt{2\_31}$。 **【数据规模与约定】** **本题采用子任务捆绑测试。** - 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）：无特殊限制。对于 $100\%$ 的数据，$1 \le n \le 50$，$n \le l \le 10000$，$1 \le r_i \le l$。 **【提示与说明】** **题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #2](https://hsin.hr/coci/contest2_tasks.pdf) _Task 4 Magneti_。** **本题分值按 COCI 原题设置，满分 $110$。**