配点 : $1100$ 点

問題文

ニワンゴ君は半開区間 $[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$ が覆っている領域が異なるものが存在することを指します。

制約

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

入力

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

$N$ $X$

$L_1$ $L_2$ $\ldots$ $L_N$

出力

答えを出力せよ。

3 3
1 1 2

10

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

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

134796357

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