题目描述

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

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

输入格式

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

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

输出格式

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

1 10
10

10

4 4
1 1 1 1

24

3 4
1 2 1

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

【提示与说明】

题目译自 COCI 2021-2022 CONTEST #2 Task 4 Magneti。

本题分值按 COCI 原题设置，满分 $110$。