#213. 种花

种花

题目描述

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

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

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

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

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

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

输入格式

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

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

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

接下来 nn 行,每行包含一个长度为 mm 且仅包含 0011 的字符串,其中第 ii 个串的第 jj 个字符表示 ai,ja_{i,j},即花园里的第 ii 行第 jj 列是不是一个土坑。

输出格式

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

样例 #1

样例输入 #1

1 0
4 3 1 1
001
010
000
000

样例输出 #1

4 2

提示

【样例 1 解释】

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

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

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

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

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

【样例 2】

见选手目录下的 plant2.inplant2.ans

【样例 3】

见选手目录下的 plant3.inplant3.ans

【数据范围】

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

测试点编号 nn mm c=c= f=f= 特殊性质 测试点分值
11 1000\leq 1000 00 11
22 =3=3 =2=2 11 11 22
33 =4=4 33
44 1000\leq 1000 44
55 1000\leq 1000 A
66 B 66
77 10\leq 10 1010
88 20\leq 20 66
99 30\leq 30
1010 50\leq 50 88
1111 100\leq 100 1010
1212 200\leq 200 66
1313 300\leq 300
1414 500\leq 500 88
1515 1000\leq 1000 00 66
1616 11 1414

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

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