P6453 [COCI 2008/2009 #4] PERIODNI

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$. #

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 one integer on a single line, representing the number of valid placements modulo $10^9+7$. #

#### 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](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #4](https://hsin.hr/coci/archive/2008_2009/contest4_tasks.pdf) *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](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #4](https://hsin.hr/coci/archive/2008_2009/contest4_tasks.pdf) *T6 PERIODNI***。 Translated by ChatGPT 5