问题描述

Ringo 对现代艺术产生了兴趣。他决定在 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)$ 被涂白色，其他（最外层）方块被涂黑色。

Ringo 在最外层的某些方块上安排了人员，面向内部。具体而言，人员的安排由四个字符串 $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)$ 上放置一个朝上的人；否则不做任何操作。

每个人都有足够数量的非白色颜料。没有两个人拥有相同颜色的颜料。

人员布局示例（为了方便，将黑色方块显示为灰色）

Ringo 在人员离场之前重复以下操作序列。

• 选择仍在会场内的一个人员。
• 选中的人员在其面前的方块是白色时重复以下操作：向前移动一个方块，并用他/她的颜料涂色进入的方块。当其面前的方块不是白色时，停止该操作。
• 人员现在离场。

棋盘绘制的示例

在过程结束时，Ringo 能够得到多少种不同的棋盘状态？将计数结果对 $998244353$ 取模。

约束条件

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

---

输入

输入以以下格式从标准输入给出：

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

输出

输出 Ringo 在过程结束时能够得到的不同棋盘状态的数量，对 $998244353$ 取模。

---

示例输入1

2 2
10
01
10
01

示例输出1

6

如下图所示，有六种可能的状态。

---

示例输入2

2 2
11
11
11
11

示例输出2

32

---

示例输入3

3 4
111
111
1111
1111

示例输出3

1276

---

示例输入4

17 21
11001010101011101
11001010011010111
111010101110101111100
011010110110101000111

示例输出4

548356548

请务必对计数结果取模 $998244353$。

---

示例输入5

3 4
000
101
1111
0010

示例输出5

21

---

示例输入6

9 13
111100001
010101011
0000000000000
1010111111101

示例输出6

177856

---

示例输入7

23 30
01010010101010010001110
11010100100100101010101
000101001001010010101010101101
101001000100101001010010101000

示例输出7

734524988