#215195. 过河卒

建议评棕。

Yuki 有一个 行 列的棋盘，行的下标为 ，列的下标为 。

棋盘上第 行第 列的格子用 表示，每个格子的颜色可能为白色或黑色，以 表示， 则表示白色， 则表示黑色。保证棋盘最外围一圈的格子颜色为白色，即保证 。

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

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

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

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

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

本题有多组测试数据。

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

对于每组测试数据：

• 第一行包含两个正整数 。
• 接下来 行，第 行包含一个长度为 的 串 。

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

样例输入 1

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

样例输出 1

3
3
4

样例 1 解释

该样例共有 组测试数据。

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

• 不放车；
• 在 放车；
• 在 放车。

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

• 不放车；
• 在 放车；
• 在 放车；

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

• 不放车；
• 在 放车；
• 在 放车；
• 在 放车。

样例 2

见附加文件中的 与 。

该样例共有 组测试数据。

其中第 组测试数据满足 ，第 组测试数据满足 ，，第 组测试数据满足 ，。

样例 3

见附加文件中的 与 。

该样例共有 组测试数据。该样例所有测试数据满足 。

其中第 组测试数据满足 ，第 组测试数据满足 ，第 组测试数据满足 。

样例 4

见附加文件中的 与 。

该样例共有 组测试数据。

其中第 组测试数据满足 ，第 组测试数据满足 ，第 组测试数据满足 。

数据范围

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

• ；
• ；
• 。

对于 为奇数的测试点，保证 。

::cute-table{tuack}

特殊性质：对于所有 ，保证 。