65000 - [NOIP2022] 种花plant

通过次数

5

提交次数

6

Time Limit : 1 秒
Memory Limit : 128 MB

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

花园可以看作有 n\times m 个位置的网格图,从上到下分别为第 1 到第 n 行,从左到右分别为第 1 列到第 m 列,其中每个位置有可能是土坑,也有可能不是,可以用 a_{i,j} = 1 表示第 i 行第 j 列这个位置有土坑,否则用 a_{i,j} = 0 表示这个位置没土坑。

一种种花方案被称为 \texttt{C-} 的,如果存在 x_1, x_2 \in [1, n],以及 y_0, y_1, y_2 \in [1, m],满足 x_1 + 1 < x_2,并且 y_0 < y_1, y_2 \leq m,使得第 x_1 的第 y_0 到第 y_1 、第 x_2 的第 y_0 到第 y_2 以及第 y_0 的第 x_1 到第 x_2 不为土坑,且只在上述这些位置上种花。

一种种花方案被称为 \texttt{F-} 的,如果存在 x_1, x_2, x_3 \in [1, n],以及 y_0, y_1, y_2 \in [1, m],满足 x_1 + 1 < x_2 < x_3,并且 y_0 < y_1, y_2 \leq m,使得第 x_1 的第 y_0 到第 y_1 、第 x_2 的第 y_0 到第 y_2 以及第 y_0 的第 x_1 到第 x_3 不为土坑,且只在上述这些位置上种花。

样例一解释中给出了 \texttt{C-} 形和 \texttt{F-} 形种花方案的图案示例。

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

Input

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

接下来一共 T 组数据,在每组数据中:

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

接下来 n 行,每行包含一个长度为 m 且仅包含 01 的字符串,其中第 i 个串的第 j 个字符表示 a_{i,j},即花园里的第 i 行第 j 列是不是一个土坑。

Output

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

Examples

Input

1 0
4 3 1 1
001
010
000
000

Output

4 2

Hint

【样例 1 解释】

四个 \texttt{C-} 形种花方案为:

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

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

类似的,两个 \texttt{F-} 形种花方案为:

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

【数据范围】

对于所有数据,保证:1 \leq T \leq 51 \leq n, m \leq 10^30 \leq c, f \leq 1a_{i,j} \in {0, 1}

测试点编号nmc=f=特殊性质测试点分值
1\leq 1000\leq 1000001
2=3=2112
3=4=2113
4\leq 1000=2114
5\leq 1000\leq 100011A4
6\leq 1000\leq 100011B6
7\leq 10\leq 101110
8\leq 20\leq 20116
9\leq 30\leq 30116
10\leq 50\leq 50118
11\leq 100\leq 1001110
12\leq 200\leq 200116
13\leq 300\leq 300116
14\leq 500\leq 500118
15\leq 1000\leq 1000106
16\leq 1000\leq 10001114

特殊性质 A:\forall 1 \leq i \leq n, 1 \leq j \leq \left\lfloor \frac{m}{3} \right\rfloora_{i, 3 j} = 1

特殊性质 B:\forall 1 \leq i \leq \left\lfloor \frac{n}{4} \right\rfloor, 1 \leq j \leq ma_{4 i, j} = 1