P7716 "EZEC-10" Covering

You are given an $n \times m$ chessboard and $k$ pieces of paper of size $1 \times 2$, numbered from $1$ to $k$. You may choose any number of pieces within $[l, r]$, and place them onto the chessboard one by one in increasing order of their numbers. Each piece can be placed either horizontally or vertically. **Note: pieces placed later will cover pieces placed earlier.** Given the number of the piece covering each cell on the final board, find the number of different valid plans, modulo $10^9 + 7$. **Two plans are the same if and only if they choose the same number of pieces, the same piece numbers, and the placement position of every piece is the same.**

The first line contains an integer $T$, the number of testdata groups. For each testdata group: - The first line contains five integers $n, m, k, l, r$. - The next $n$ lines each contain $m$ integers, describing the piece number on each cell in the final board. If a cell is not covered, the number is $0$. - **The testdata guarantees that at least one feasible plan exists.**

For each testdata group: - Output one integer per line, the number of plans modulo $10^9 + 7$.

**[Sample 1 Explanation]** It is not hard to see that you can only take pieces numbered $1, 2, 3$. In this case, there are $2$ plans: $1:(1,1)\to (1,2)$, $2:(1,2)\to (2,2)$, $3:(2,1)\to (2,2)$; $1:(1,1)\to (2,1)$, $2:(1,2)\to (2,2)$, $3:(2,1)\to (2,2)$. **[Constraints and Conventions]** **This problem uses bundled tests.** - Subtask 1 (5 points): $r = 1$. - Subtask 2 (10 points): $n, m, k \le 5$. - Subtask 3 (15 points): $l = k$. - Subtask 4 (20 points): $n \times m \le 10^3$. - Subtask 5 (50 points): no special restrictions. For $100\%$ of the testdata, $1 \le T \le 10$, $2 \le n, m, k \le 10^3$, $1 \le l \le r \le k$. Translated by ChatGPT 5