Description

As shown in the figure, you are given a grid consisting of $n$ columns, and the bottoms of all columns are aligned.

You need to place $k$ identical numbers into it, but no two numbers may be in the same row or the same column.

For example, in the figure, placing b is invalid because the two b are in the same column. However, placing a is valid, because although the two a are on the same row, there is a gap between them, so it is not considered invalid.

Compute the total number of valid placements modulo $10^9+7$.

Input Format

The first line contains two integers $n, k$, representing the number of columns in the grid and the number of identical numbers to place.

The second line contains $n$ integers. The $i$-th integer (from left to right) represents the height (number of levels) of the $i$-th column.

Output Format

Output one integer on a single line, representing the number of valid placements modulo $10^9+7$.

3 3
2 1 3

2

4 1
1 2 3 4

10

5 2
2 3 1 2 4

43

3 2
999999 999999 999999

990979013

Hint

Constraints

• For $40\%$ of the testdata, the input numbers are all less than $15$.
• For $70\%$ of the testdata, the input numbers are all less than $100$.
• For $100\%$ of the testdata, $1 \le n, k \le 500$, and the column heights do not exceed $10^6$.

Notes

This problem is translated from COCI2008-2009 CONTEST #4 T6 PERIODNI。

Input Format

The first line contains two integers $n, k$, representing the number of columns in the grid and the number of identical numbers to place.

The second line contains $n$ integers. The $i$-th integer (from left to right) represents the height (number of levels) of the $i$-th column.

Output Format

Output one integer on a single line, representing the number of valid placements modulo $10^9+7$.

Hint

Constraints

• For $40\%$ of the testdata, the input numbers are all less than $15$.
• For $70\%$ of the testdata, the input numbers are all less than $100$.
• For $100\%$ of the testdata, $1 \le n, k \le 500$, and the column heights do not exceed $10^6$.

Notes

This problem is translated from COCI2008-2009 CONTEST #4 T6 PERIODNI。

Translated by ChatGPT 5