Problem Description

Given a table consisting of $n$ columns, where the bottom of each column is aligned.

You need to fill in $k$ identical numbers within this table, ensuring that no two numbers are in the same row or the same column.

For example, the placement of b in the diagram is illegal because two bs are in the same column. However, the placement of a is legal because, although these two as are in the same row, they are separated, so it is not considered illegal.

Calculate the total number of valid filling schemes modulo $10^9+7$.

Input Format

The first line contains two integers $n$ and $k$, representing the number of columns in the table and the number of identical numbers to be placed, respectively.

The second line contains $n$ integers, where the $i$-th integer represents the height of the $i$-th column from left to right.

Output Format

Output a single integer, which is the total number of valid filling schemes modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3 3
2 1 3

Sample Output #1

2

Sample Input #2

4 1
1 2 3 4

Sample Output #2

10

Sample Input #3

5 2
2 3 1 2 4

Sample Output #3

43

Sample Input #4

3 2
999999 999999 999999

Sample Output #4

990979013

Notes

Data Size and Constraints

• For $40\%$ of the data, the input numbers are all less than $15$.
• For $70\%$ of the data, the input numbers are all less than $100$.
• For $100\%$ of the data, $1 \le n, k \le 500$, and the height of the columns does not exceed $10^6$.

Note

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

见题面 Input 部分

见题面 Output 部分