Problem Statement

Ebi-chan is studying sorting. One day, she found a strange sort called "tsutaj sort". Apparently, it is used to quickly obtain a sequence that is roughly in ascending order.

When a sequence $a$ is tsutaj-sorted, it always returns a sequence $a'$ whose inversion number is at most $K$. Here, the inversion number is the number of pairs $(i, j)$ such that $i < j$ and $a_i' > a_j'$.

Ebi-chan is curious how many possible sequences there are after tsutaj sort. Find the total number of rearrangements of the given sequence whose inversion number is at most $K$, modulo $1,000,000,007$.

Input

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

The input is given in $2$ lines.

The $1$st line contains the length $N$ of the sequence and the upper bound $K$ on the inversion number of the sorted sequence.

The $2$nd line contains the sequence $a$. The $i$-th element is $a_i$.

Constraints

• $1 \leq N \leq 300$
• $0 \leq K \leq \frac{N(N-1)}{2}$
• $1 \leq a_i \leq 10^9$
• All $a_i$ are distinct. That is, if $i \neq j$ then $a_i \neq a_j$.

Output

Output in $1$ line the total number of rearrangements of the given sequence whose inversion number is at most $K$, modulo $1,000,000,007$.

Sample

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