AT_

题目描述

对现代美术产生兴趣的りんごさん，决定在 CODE FESTIVAL 2017 的会场上，用 $N+2$ 行 $M+2$ 列的棋盘和几个人来创作一幅画。

棋盘的第 $i+1$ 行、第 $j+1$ 列的格子用整数对 $(i,j)$ 表示。也就是说，左上角的格子是 $(0,0)$，右下角的格子是 $(N+1,M+1)$。最开始，满足 $1 \leq x \leq N, 1 \leq y \leq M$ 的格子 $(x,y)$ 是白色，其余（外围）的格子为黑色。

りんごさん在棋盘的外周若干格子上，朝向内部放置了人。更为严谨地说，放置方式由四个字符串 $A,B,C,D$ 描述，并按如下方式进行：

• 对于每一行（不包括边界），如果 $A$ 的第 $i$（$1 \leq i \leq N$）个字符为1，就在 $(i,0)$ 格子放置一个朝右的人。否则，不做操作。
• 对于每一行（不包括边界），如果 $B$ 的第 $i$（$1 \leq i \leq N$）个字符为1，就在 $(i,M+1)$ 格子放置一个朝左的人。否则，不做操作。
• 对于每一列（不包括边界），如果 $C$ 的第 $i$（$1 \leq i \leq M$）个字符为1，就在 $(0,i)$ 格子放置一个朝下的人。否则，不做操作。
• 对于每一列（不包括边界），如果 $D$ 的第 $i$（$1 \leq i \leq M$）个字符为1，就在 $(N+1,i)$ 格子放置一个朝上的人。否则，不做操作。

每个人都携带有充足的非白色油漆，并且任意两个人所用油漆的颜色都各不相同。

人们的放置例（为了方便，黑色格子用灰色表示）

りんごさん反复执行以下一系列操作，直到所有人都离开会场为止：

• 选择一位仍未离开会场的人。
• 如果这位所面前的格子是白色，就朝自己面朝的方向前进一步，并把前进到的格子涂成所持有颜料的颜色。若面前的格子不是白色，则停止动作。
• 动作结束的人离开会场。

涂色情况的例子

りんごさん能制作的最终棋盘涂色情况有多少种？请输出对 $998244353$ 取模的结果。

这里，两个涂色方案只要存在某个格子的颜色不同，就被认为是不同方案。

输入格式

输入按以下格式从标准输入给出。

$N\ M\ A\ B\ C\ D$

输出格式

请输出最终棋盘涂色情况的总数，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

2 2
10
01
10
01

输出 #1

6

输入输出样例 #2

输入 #2

2 2
11
11
11
11

输出 #2

32

输入输出样例 #3

输入 #3

3 4
111
111
1111
1111

输出 #3

1276

输入输出样例 #4

输入 #4

17 21
11001010101011101
11001010011010111
111010101110101111100
011010110110101000111

输出 #4

548356548

输入输出样例 #5

输入 #5

3 4
000
101
1111
0010

输出 #5

21

输入输出样例 #6

输入 #6

9 13
111100001
010101011
0000000000000
1010111111101

输出 #6

177856

输入输出样例 #7

输入 #7

23 30
01010010101010010001110
11010100100100101010101
000101001001010010101010101101
101001000100101001010010101000

输出 #7

734524988

说明/提示

限制条件

• $1 \leq N, M \leq 10^5$
• $|A| = |B| = N$
• $|C| = |D| = M$
• $A,B,C,D$ 均由0和1组成

样例解释 1

有 $6$ 种不同的涂色方式。

样例解释 4

不要忘记对 $998244353$ 取模。

由 ChatGPT 5 翻译