← 返回题目列表

AtCoder · code_festival_2017_quala_e

E. 现代绘画

中文机器翻译题面 查看原题

分数: 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