#P18626. Repair the Artwork

Repair the Artwork

Repair the Artwork

DreamGrid 有一条由 nn 个格子组成的纸带,格子从左到右编号为 1,…,n1,\ldots,n。有些格子画着他自己的图案,有些格子被 BaoBao 画上了别的图案,还有些格子是空的。他想擦掉 BaoBao 的全部图案,同时保留自己的所有图案。

每次操作可以选择一个非空区间 [l,r][l,r],满足 1≤l≤r≤n1\le l\le r\le n,且区间内的每个格子要么是空格,要么画着 BaoBao 的图案。然后把这个区间内的所有格子变成空格。

问:恰好进行 mm 次操作,将所有 BaoBao 图案都擦掉的操作序列共有多少种?答案对 109+710^9+7 取模。

设两种操作序列的区间分别为 (l1,r1),…,(lm,rm)(l_1,r_1),\ldots,(l_m,r_m) 和 (l1′,r1′),…,(lm′,rm′)(l'_1,r'_1),\ldots,(l'_m,r'_m)。只要存在一个 ii 使得 li≠li′l_i\ne l'_i 或 ri≠ri′r_i\ne r'_i,这两个操作序列就不同。操作顺序有区别,同一个合法区间可以反复选择;选择一个已经全空的非空区间也是合法操作。

输入格式

第一行包含整数 TT,表示测试用例数。

每个测试用例的第一行包含两个整数 n,mn,m,分别表示纸带格子数和操作次数。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n:

  • ai=0a_i=0:这个格子为空;
  • ai=1a_i=1:这个格子画着 DreamGrid 的图案,不能擦掉;
  • ai=2a_i=2:这个格子画着 BaoBao 的图案,必须最终擦掉。

数据范围

  • 1≤T≤10001\le T\le1000;
  • 1≤n≤1001\le n\le100;
  • 1≤m≤1091\le m\le10^9;
  • ai∈{0,1,2}a_i\in\{0,1,2\};
  • 在一个输入文件中,至多 5050 个测试用例满足 n>50n>50。

输出格式

对每个测试用例输出一行,包含合法操作序列数对 109+710^9+7 取模的结果。

样例输入 1

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

样例输出 1

8
3
1

样例解释

第一个测试用例有三个可选非空区间:[1,1]、[2,2]、[1,2]。两次选择共有九种有序序列,只有两次都选[2,2]时没有擦掉第一个格子,所以答案为8。

第二个测试用例中,不能跨过第二个格子。两次操作都选[1,1],或分别选[1,1]、[3,3]并交换先后顺序,共三种。第三个测试用例只能选[1,1]。