<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

269. Rooks
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Let's define a board as a finite subset of infinite chessboard cells. The (b_1, b_2, ..., b_n) board is the board with n left-aligned rows. The i-th line consists of b_i sequential cells. For example, (1, 4, 3, 5) board looks as follows:

 
 	 	 	 
 	 	 
 	 	 	 	 


The rook can be placed on any cell of the board. The rooks disposition is called peaceful if and only if no two rooks stay on the same vertical or horizontal line (no matter if all cells between them belong to the (b_1, b_2, ..., b_n) board or not).
Your task is to find a number of peaceful dispositions of k rooks for the (b_1, b_2, ..., b_n) board.

Input
The first line of the input file contains two integer numbers n and k (1 <= n, k <= 250). The second line contains n space-delimited numbers (b_1, b_2, ..., b_n) (1 <= b_i <= 250, i=1..n).

Output
Write to the output single integer -- number of different peaceful rooks dispositions on the given board.

Sample test(s)

Input
Test #1
2 2
2 3

Test #2
3 3
2 1 2

Output
Test #1
4

Test #2
0
Author:	Michael R. Mirzayanov
Resource:	ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
Date:	Saratov, October 7, 2004

<|response|>
1. Abridged Problem Statement  
We have an “irregular” chessboard with n rows, where row i has b_i contiguous cells in columns 1 through b_i. Count the number of ways to place exactly k rooks so that no two attack each other (i.e., no two share a row or a column).

2. Key Observations  
- Any peaceful arrangement uses k distinct rows and k distinct columns, with exactly one rook per chosen row and column.  
- If we process rows in some order and maintain how many rooks we’ve already placed (say j – 1), those rooks occupy j – 1 distinct columns.  
- In the next row of length v, if we want to place the j-th rook there, we must choose one of the columns 1…v that isn’t already used. That gives (v – (j–1)) choices (if positive).  
- Sorting the row lengths b in non-decreasing order ensures when we consider a row of length v, earlier rows have no larger length, but actually sorting is only for stability of the DP transitions.

3. Full Solution Approach  
a. Read n, k and the array b of length n.  
b. Sort b in non-decreasing order.  
c. Let dp[j] = number of ways to place exactly j rooks so far (using j distinct columns). Initialize dp[0] = 1, dp[1…k] = 0.  
d. For each row length v in b:  
   - For j = k down to 1:  
     • Compute free = v – (j–1).  
     • If free > 0, then we can place the j-th rook in this row in free ways, so  
         dp[j] += dp[j–1] * free  
     • Otherwise do nothing (no valid way to get j rooks using this row).  
e. After processing all n rows, dp[k] is the answer.  

Time complexity is O(n·k). Space is O(k). Because answers can be very large, we use arbitrary‐precision arithmetic.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
// Use big–integer type
using BigInt = boost::multiprecision::cpp_int;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> b(n);
    for(int i = 0; i < n; i++){
        cin >> b[i];
    }

    // Sort row lengths
    sort(b.begin(), b.end());

    // dp[j] = number of ways to place j rooks so far
    vector<BigInt> dp(k+1);
    dp[0] = 1;  // base case: zero rooks in one way

    // Process each row
    for(int v : b){
        // Update dp in reverse to avoid overwriting dp[j-1]
        for(int j = k; j >= 1; j--){
            // number of columns free in this row
            int freeCols = v - (j - 1);
            if(freeCols > 0){
                // we can place the j-th rook here in freeCols ways
                dp[j] += dp[j-1] * freeCols;
            }
        }
    }

    // Output the count for exactly k rooks
    cout << dp[k] << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
def main():
    import sys
    data = sys.stdin.read().split()
    n, k = map(int, data[:2])
    b = list(map(int, data[2:]))

    # Sort row lengths
    b.sort()

    # dp[j] = number of ways to place j rooks so far
    dp = [0] * (k + 1)
    dp[0] = 1  # one way to place zero rooks

    # Process each row of length v
    for v in b:
        # Update in reverse to use previous values
        for j in range(k, 0, -1):
            free_cols = v - (j - 1)
            if free_cols > 0:
                dp[j] += dp[j-1] * free_cols

    # Print the result for exactly k rooks
    print(dp[k])

if __name__ == "__main__":
    main()
```