#2004. 「NOIP 2022」种花

小 C 决定在他的花园里种出 字样的图案，因此他想知道 和 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。

花园可以看作有 个位置的网格图，从上到下分别为第 到第 行，从左到右分别为第 列到第 列，其中每个位置有可能是土坑，也有可能不是，可以用 表示第 行第 列这个位置有土坑，否则用 表示这个位置没土坑。

一种种花方案被称为 形的，如果存在 ，以及 ，满足 ，并且 ，使得第 行的第 到第 列、第 行的第 到第 列以及第 列的第 到第 行都不为土坑，且只在上述这些位置上种花。

一种种花方案被称为 形的，如果存在 ，以及 ，满足 ，并且 ，使得第 行的第 到第 列、第 行的第 到第 列以及第 列的第 到第 行都不为土坑，且只在上述这些位置上种花。

样例一解释中给出了 形和 形种花方案的图案示例。

现在小 C 想知道，给定 以及表示每个位置是否为土坑的值 ， 形和 形种花方案分别有多少种可能？由于答案可能非常之大，你只需要输出其对 取模的结果即可，具体输出结果请看输出格式部分。

从文件 plant.in 中读入数据。

第一行包含两个整数 ，分别表示数据组数和测试点编号。如果数据为样例则保证 。

接下来一共 组数据，在每组数据中：

第一行包含四个整数 ，其中 分别表示花园的行数、列数，对于 的含义见输出格式部分。

接下来 行，每行包含一个长度为 且仅包含 和 的字符串，其中第 个串的第 个字符表示 ，即花园里的第 行第 列是不是一个土坑。

输出到文件 plant.out 中。

设花园中 形和 形的种花方案分别有 和 种，则你需要对每一组数据输出一行用一个空格隔开的两个非负整数，分别表示 ， ，其中 表示 对 取模后的结果。

样例 1 输入

1 0
4 3 1 1
001
010
000
000

样例 1 输出

4 2

样例 1 解释

四个 形种花方案为：

**1 **1 **1 **1
*10 *10 *10 *10
**0 *** *00 *00
000 000 **0 ***

其中 表示在这个位置种花。注意 的两横可以不一样长。

类似的，两个 形种花方案为：

**1 **1
*10 *10
**0 ***
*00 *00

样例 2

见附件下的 plant/plant2.in 与 plant/plant2.ans。

样例 3

见附件下的 plant/plant3.in 与 plant/plant3.ans。

对于所有数据，保证：，，，。

特殊性质 A：，；

特殊性质 B：，；