题目背景

建议评棕。

题目描述

Yuki 有一个 $n+2$ 行 $m+2$ 列的棋盘，行的下标为 $0 \sim n+1$，列的下标为 $0 \sim m+1$。

棋盘上第 $i$ 行第 $j$ 列的格子用 $(i,j)$ 表示，每个格子的颜色可能为白色或黑色，以 $s_{i,j}$ 表示，$s_{i,j} = \texttt0$ 则表示白色，$s_{i,j} = \texttt1$ 则表示黑色。保证棋盘最外围一圈的格子颜色为白色，即保证 $s_{0,i}=s_{n+1,i}=s_{i,0}=s_{i,m+1}=\texttt0$。

Yuki 打算在棋盘上摆放若干个车。对于格子 $(i,j)$，它被称作安全的，当且仅当存在至少一个车位于第 $i$ 行或第 $j$ 列，且格子 $(i,j)$ 上不存在车。

Yuki 对车的摆放方案有如下要求：

• 所有车都位于黑色格子上；
• 任意两个车都不位于同一行或同一列；
• 卒从棋盘的第 $0$ 行出发，不可以在只经过安全的格子的情况下到达棋盘的第 $n+1$ 行。

其中，卒的行走方式为：设当前卒的位置为 $(i,j)$，那么它可以走到 $(i+1,j),(i,j-1),(i,j+1)$ 中的任意一个格子，只要这个目的地在棋盘内。

Yuki 需要你帮助她求出满足条件的摆放方案的数量。由于答案可能较大，你只需要求出答案对 $10^9+7$ 取模后的结果。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $t,c$，分别表示测试数据组数和测试点编号。样例满足 $c=0$。

对于每组测试数据：

• 第一行包含两个正整数 $n,m$。
• 接下来 $n$ 行，第 $i$ 行包含一个长度为 $m$ 的 $\texttt 01$ 串 $s_{i,1},\dots,s_{i,m}$。

输出格式

对于每组测试数据，输出一行，包含一个整数表示答案。

3 0
2 2
11
00
2 2
01
01
3 3
100
000
001

3
3
4

提示

样例 1 解释

该样例共有 $3$ 组测试数据。

对于第 $1$ 组测试数据，$3$ 种合法方案分别为：

• 不放车；
• 在 $(1,1)$ 放车；
• 在 $(1,2)$ 放车。

对于第 $2$ 组测试数据，$3$ 种合法方案分别为：

• 不放车；
• 在 $(1,2)$ 放车；
• 在 $(2,2)$ 放车；

对于第 $3$ 组测试数据，$4$ 种合法方案分别为：

• 不放车；
• 在 $(1,1)$ 放车；
• 在 $(3,3)$ 放车；
• 在 $(1,1),(3,3)$ 放车。

样例 2

见附加文件中的 $\boldsymbol{zu2.in}$ 与 $\boldsymbol{zu2.ans}$。

该样例共有 $3$ 组测试数据。

其中第 $1$ 组测试数据满足 $n,m \le 4$，第 $2$ 组测试数据满足 $n \le 100$，$m \le 4$，第 $3$ 组测试数据满足 $n \le 200$，$m \le 8$。

样例 3

见附加文件中的 $\boldsymbol{zu3.in}$ 与 $\boldsymbol{zu3.ans}$。

该样例共有 $3$ 组测试数据。该样例所有测试数据满足 $s_{i,j} = 1$。

其中第 $1$ 组测试数据满足 $n,m \le 80$，第 $2$ 组测试数据满足 $n,m \le 300$，第 $3$ 组测试数据满足 $n,m \le 1500$。

样例 4

见附加文件中的 $\boldsymbol{zu4.in}$ 与 $\boldsymbol{zu4.ans}$。

该样例共有 $3$ 组测试数据。

其中第 $1$ 组测试数据满足 $n,m \le 80$，第 $2$ 组测试数据满足 $n,m \le 500$，第 $3$ 组测试数据满足 $n,m \le 3000$。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 3$；
• $1 \le n,m \le 3000$；
• $s_{i,j} \in \{\texttt0,\texttt1\}$。

对于 $\boldsymbol c$ 为奇数的测试点，保证 $\boldsymbol{n=m}$。

::cute-table{tuack}

测试点编号	$n \le$	$m \le$	特殊性质
$1 \sim 4$	$100$	$4$	否
$5 \sim 8$	$200$	$8$
$9,10$	$1$	$1500$
$11,12$	$1500$	$1$
$13,14$	$80$		是
$15,16$	$300$
$17,18$	$1500$
$19 \sim 21$	$80$		否
$22,23$	$500$
$24,25$	$3000$

特殊性质：对于所有 $i \in [1,n],j \in [1,m]$，保证 $s_{i,j}=\texttt1$。