题目描述

ニワンゴ君は半開区間 $[0,X)$ で表される土地を購入しました。

ニワンゴ君はこの土地に $N$ 枚のシートを敷くことにしました。シートには $1,2,\ \ldots,\ N$ と番号が振られており、これらは区別されます。 シート $i$ は、$0\ \leq\ j\ \leq\ X\ -\ L_i$ を満たす整数 $j$ を選んで $[j,\ j\ +\ L_i)$ を覆うように敷くことができます。

$[0,X)$ にシートに覆われていない座標が存在しないようなシートの敷き方の総数を $10^9+7$ で割ったあまりを求めてください。 ただし、$2$ つの敷き方が異なるとは、整数 $i(1\ \leq\ i\ \leq\ N)$ であって、シート $i$ が覆っている領域が異なるものが存在することを指します。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $X$ $L_1$ $L_2$ $\ldots$ $L_N$

输出格式

答えを出力せよ。

题目大意

有一个区间 $[0, X)$，你有一个数组 $L_1, L_2, \cdots, L_n$。对于每个 $i$，你可以选择一个整数 $j$ 满足 $0 \le j \le X- L_i$，并覆盖 $[j, j + L_i)$ 这个区间。问有多少种方案，使得整个区间都被覆盖，方案数对 $10^9 + 7$ 取模。

3 3
1 1 2

10

18 477
324 31 27 227 9 21 41 29 50 34 2 362 92 11 13 17 183 119

134796357

提示

制約

• $1\ \leq\ N\ \leq\ 100$
• $1\ \leq\ L_i\ \leq\ X\ \leq\ 500$
• 入力中の値はすべて整数

Sample Explanation 1

- 区間全体が覆われているかどうかを無視すると、シートの敷き方の総数は $18$ 通り考えられます。 - そのうち、$[0,1)$ が覆われないような敷き方が $4$ 通り、$[2,3)$ が覆われないような敷き方が $4$ 通りあります。 - それ以外の敷き方は $[0,3)$ を全てシートで覆うことができるので、答えは $10$ 通りです。

Sample Explanation 2

- 敷き方の総数を $10^9+7$ で割ったあまりを求めてください。