問題文

えびちゃんはソートの勉強をしています。ある日、「tsutaj ソート」という変なソートを見つけました。どうやら、だいたい昇順に並んでいる数列を高速に得るときに使うようです。

数列 $a$ を tsutaj ソートすると、必ず転倒数が $K$ 以下であるような数列 $a'$ が返ってきます。ここで転倒数とは、$i < j$ であって $a_i' > a_j'$ であるような組 $(i, j)$ の個数です。

えびちゃんは、tsutaj ソート後の数列が何通りあるか気になっています。与えられた数列を並び替えたもので、転倒数が $K$ 以下のものの総数を $1,000,000,007$ で割った余りを求めてください。

入力

$N$ $K$
$a_1$ $a_2$ $\dots$ $a_N$

入力は $2$ 行で与えられる。

$1$ 行目では、数列の長さ $N$、ソート後の数列の転倒数の上限 $K$ が与えられる。

$2$ 行目では、数列 $a$ が与えられる。$i$ 番目の要素は $a_i$ である。

制約

• $1 \leq N \leq 300$
• $0 \leq K \leq \frac{N(N-1)}{2}$
• $1 \leq a_i \leq 10^9$
• $a_i$ は相異なる。すなわち、 $i \neq j$ ならば $a_i \neq a_j$

出力

与えられた数列を並び替えたもので、転倒数が $K$ 以下のものの総数を $1,000,000,007$ で割った余りを $1$ 行に出力せよ。

サンプル

3 1
1 2 3

3

5 7
1 4 5 8 2

106

13 78
3 1 4 15 9 2 6 5 35 89 7 93 23

227020758