分数: 1600 点
问题陈述
林戈对现代艺术产生了兴趣。他决定在黑板上画一幅大图 N+2 行和 M+2 2017 年 CODE FESTIVAL 会场内由一些人建造的广场柱。
广场 (i+1)第行和 (j+1)棋盘中的第列由一对整数表示 (i,j)。也就是说,左上角的正方形是 (0,0),右下角的方块是 (N+1,M+1)。 最初,正方形 (x,y) 满意 1 \leq x \leq N 和 1 \leq y \leq M 被漆成白色,其他(最外面的)方块被漆成黑色。
林戈把人安排在最外面的一些方格上,面朝内。 更具体地说,人的排列由四个字符串表示 A, B, C 和 D,如下:
- 对于除顶部和底部之外的每一行,如果 i- 第一个字符 (1 \leq i \leq N) in A is
1,将一个人面朝右边放置在广场上 (i,0);否则,什么也不做。 - 对于除顶部和底部之外的每一行,如果 i- 第一个字符 (1 \leq i \leq N) in B is
1,将一个面向左的人放置在广场上 (i,M+1);否则,什么也不做。 - 对于除最左边和最右边之外的每一列,如果 i- 第一个字符 (1 \leq i \leq M) in C is
1,将一个人面朝下放置在广场上 (0,i);否则,什么也不做。 - 对于除最左边和最右边之外的每一列,如果 i- 第一个字符 (1 \leq i \leq M) in D is
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