P15060 过河卒

建议评棕。

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

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

### 样例 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$ | $80$ | 是 | | $15,16$ | $300$ | $300$ | 是 | | $17,18$ | $1500$ | $1500$ | 是 | | $19 \sim 21$ | $80$ | $80$ | 否 | | $22,23$ | $500$ | $500$ | 否 | | $24,25$ | $3000$ | $3000$ | 否 | 特殊性质：对于所有 $i \in [1,n],j \in [1,m]$，保证 $s_{i,j}=\texttt1$。