Problem Description

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.

Input Format

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.

Output Format

For each testdata group:

• Output one integer per line, the number of plans modulo $10^9 + 7$.

1
2 2 4 2 4
1 2
3 3

2

2
2 2 4 2 3
0 0
2 2
2 2 4 2 2
1 1
3 3

1
1

Hint

[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