题目描述

给你一个 $n\times m$ 的棋盘和 $k$ 张 $1\times 2$ 的纸片，编号 $1$ 到 $k$。

你可以任意选择数量在 $[l,r]$ 内的纸片，并按照编号从小到大的顺序，依次横放或竖放在棋盘上。

注意：后放的纸片会覆盖在先放的纸片上。

给定最终棋盘中每个格子上的纸片编号，求满足条件的不同方案数，并对 $10^9+7$ 取模。

两种方案相同，当且仅当两方案选择的纸片数量、纸片编号及每张纸片的摆放位置均相同。

输入格式

第一行一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行五个整数 $n,m,k,l,r$。
• 后 $n$ 行每行 $m$ 个整数，表示最终棋盘中每个格子上的纸片编号，若某格子未被覆盖则编号记为 $0$。
• 数据保证至少存在一种可行的方案。

输出格式

对于每组数据：

• 一行一个整数，表示方案数对 $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

提示

【样例 1 解释】

不难发现只能取编号为 $1,2,3$ 的纸片，此时共有 $2$ 种方案：

$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)$。

【数据规模与约定】

本题采用捆绑测试。

• 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）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le 10$，$2\le n,m,k\le 10^3$，$1\le l\le r\le k$。