luogu#P7716. 「EZEC-10」Covering

「EZEC-10」Covering

题目描述

给你一个 n×mn\times m 的棋盘和 kk1×21\times 2 的纸片,编号 11kk

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

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

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

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

输入格式

第一行一个整数 TT,表示测试数据组数。

对于每组测试数据:

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

输出格式

对于每组数据:

  • 一行一个整数,表示方案数对 109+710^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,31,2,3 的纸片,此时共有 22 种方案:

1:(1,1)(1,2)1:(1,1)\to (1,2)2:(1,2)(2,2)2:(1,2)\to (2,2)3:(2,1)(2,2)3:(2,1)\to (2,2)

1:(1,1)(2,1)1:(1,1)\to (2,1)2:(1,2)(2,2)2:(1,2)\to (2,2)3:(2,1)(2,2)3:(2,1)\to (2,2)

【数据规模与约定】

本题采用捆绑测试。

  • Subtask 1(5 points):r=1r=1
  • Subtask 2(10 points):n,m,k5n,m,k\le 5
  • Subtask 3(15 points):l=kl=k
  • Subtask 4(20 points):n×m103n\times m\le 10^3
  • Subtask 5(50 points):无特殊限制。

对于 100%100\% 的数据,1T101\le T\le 102n,m,k1032\le n,m,k\le 10^31lrk1\le l\le r\le k