题目描述

C 决定在他的花园里种出 CCF 字样的图案，因此他想知道 C 和 F 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。 花园可以看作有 $n× m$ 个位置的网格图，从上到下分别为第 $1$ 到第 $n$ 行，从左到右分别为第 $1$ 列到第 $m$ 列，其中每个位置有可能是土坑，也有可能不是，可以用 $a_{i,j} = 1$表示第 $i$ 行第 $j$ 列这个位置有土坑，否则用 $a_{i,j} = 0$ 表示这个位置没土坑。 一种种花方案被称为 C‐ 形. 的，如果存在 $x_1$, $x_2$ ∈ $[1, n]$，以及 $y_0$, $y_1$, $y_2$ ∈ $[1, m]$，满足 $x_1 + 1 < x_2$，并且$y_0 < y_1, y_2 ≤ m$，使得第 $x_1$ 行 的第 $y_0$ 到第 $y_1$ 列 、第 $x_2$ 行 的第$y_0$ 到第 $y_2$ 列以及第 $y_0$ 列的第 $x_1$ 到第 $x_2$ 行 都不 为 土 坑 ，且只在上述这些位置上种花。 一种种花方案被称为 F‐ 形的，如果存在 $x_1$, $x_2$, $x_3$ ∈ $[1, n]$，以及 $y_0$, $y_1$, $y_2$ ∈ $[1, m]$，满足 $x_1 + 1 < x_2 < x_3$，并且 $y_0$ < $y_1$, $y_2 ≤ m$，使得第 $x_1$ 行的第 $y_0$ 到第 $y_1$ 列 、第 $x_2$行 的第$y_0$ 到第 $y_2$ 列 以及第 $y_0$ 列 的第 $x_1$ 到第 $x_3$ 行 都不为土坑 ，且只在上述这些位置上种花。 样例一解释中给出了 C‐ 形和F‐ 形种花方案的图案示例。 现在小 C 想知道，给定 $n, m$ 以及表示每个位置是否为土坑的值 {$a_{i,j}$}，C‐ 形和F‐形种花方案分别有多少种可能？由于答案可能非常之大，你只需要输出其对 998244353取模的结果即可，具体输出结果请看输出格式部分。

输入

第一行包含两个整数 $T$, $id$，分别表示数据组数和测试点编号。如果数据为样例则保证 $id = 0$。 接下来一共 T 组数据，在每组数据中： 第一行包含四个整数 $n, m, c, f$，其中 $n, m$ 分别表示花园的行数、列数，对于 $c, f$的含义见输出格式部分。 接下来 $n$ 行，每行包含一个长度为 $m$ 且仅包含 $0$ 和 $1$ 的字符串，其中第 $i$ 个串的第 $j$ 个字符表示 $a_{i,j}$，即花园里的第 $i$ 行第 $j$ 列是不是一个土坑。

输出

设花园中 C‐ 形和 F‐ 形的种花方案分别有 $V_C$ 和 $V_F$ 种，则你需要对每一组数据输出一行用一个空格隔开的两个非负整数，分别表示$(c × V_C) \mod 998244353$,$(f ×V_F ) \mod 998244353$ ，其中 $a \mod P$ 表示 $a$ 对 $P$ 取模后的结果。

输入样例

1 0
4 3 1 1
001
010
000
000

输出样例

4 2

提示

【样例 1 解释】 四个 C‐ 形种花方案为：

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

其中 * 表示在这个位置种花。注意 C 的两横可以不一样长。 类似的，两个 F‐ 形种花方案为：

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

【数据范围】 对于所有数据，保证：$1 ≤ T ≤ 5$，$1 ≤ n, m ≤ 10^3$，$0 ≤ c, f ≤ 1$，$a_{i,j}$ ∈ {$0$, $1$}。

测试点编号	n	m	c =	f =	特殊性质	测试点分值
1	≤ 1000	≤ 1000	0	0	无	1
2	= 3	= 2	1	1		2
3	= 4					3
4	≤ 1000					4
5		≤ 1000			A
6					B	6
7	≤ 10	≤ 10			无	10
8	≤ 20	≤ 20				6
9	≤ 30	≤ 30
10	≤ 50	≤ 50				8
11	≤ 100	≤ 100				10
12	≤ 200	≤ 200				6
13	≤ 300	≤ 300
14	≤ 500	≤ 500				8
15	≤ 1000	≤ 1000		0		6
16				1		14

特殊性质 A: $∀1 ≤ i ≤ n$, $1 ≤ j ≤ \lfloor \frac{m}{3} \rfloor$, $a_{i,3j} = 1$。 特殊性质 B：$∀1 ≤ i ≤ \lfloor \frac{n}{4}\rfloor$, $1 ≤ j ≤ m$, $a_{4i,j} = 1$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共4个测试点，非原站或官方原始数据。总分100分。