問題文

ニワンゴ君は半開区間 $\[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$

出力

答えを出力せよ。

入力例 1

3 3
1 1 2

出力例 1

10

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

入力例 2

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

出力例 2

134796357

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