题目描述

给定 $n$ 个磁铁和 $l$ 个空位，其中相邻空位之间的距离为 $1$，每个空位可放置一个磁铁。所有 $n$ 个磁铁都必须被放置。每个磁铁可以吸引距离小于 $r_i$ 的其它磁铁。

求所有磁铁互不吸引的方案总数对 $10^9+7$ 取模的结果。

输入格式

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

第二行 $n$ 个整数 $r_i$。

输出格式

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

输入输出样例 #1

输入 #1

1 10
10

输出 #1

10

输入输出样例 #2

输入 #2

4 4
1 1 1 1

输出 #2

24

输入输出样例 #3

输入 #3

3 4
1 2 1

输出 #3

4

说明/提示

【样例 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$。