E - Modern Painting 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 1600 点

問題文

現代美術に興味を持ったりんごさんは、CODE FESTIVAL 2017 の会場に作られた N+2 行 M+2 列の盤面と、何人かの人を使って絵を描くことにしました。

盤面の上から i+1 行目、左から j+1 列目のマスは 2 つの整数の組 (i,j) であらわされます。すなわち、左上のマスが (0,0) で、右下のマスが (N+1,M+1) です。 最初、1 \leq x \leq N, 1 \leq y \leq M を満たすマス (x,y) は白で塗られており、それ以外の (外周の) マスは黒で塗られています。

りんごさんは、盤面の外周のマスのうちのいくつかに、人を内向きに配置しました。 より厳密には、配置の情報は 4 つの文字列 A,B,C,D によってあらわされ、以下のように配置が行われます。

  • 端以外の各行について、A の i(1 \leq i \leq N) 文字目が 1 のときマス (i,0) に、右を向いた人を 1 人配置する。そうでないとき、何もしない。
  • 端以外の各行について、B の i(1 \leq i \leq N) 文字目が 1 のときマス (i,M+1) に、左を向いた人を 1 人配置する。そうでないとき、何もしない。
  • 端以外の各列について、C の i(1 \leq i \leq M) 文字目が 1 のときマス (0,i) に、下を向いた人を 1 人配置する。そうでないとき、何もしない。
  • 端以外の各列について、D の i(1 \leq i \leq M) 文字目が 1 のときマス (N+1,i) に、上を向いた人を 1 人配置する。そうでないとき、何もしない。

各人はそれぞれ、白でない色のペンキを充分な量持っています。どの相異なる 2 人の持っているペンキの色も、互いに異なります。

人の配置の例(便宜上、黒く塗られたマスを灰色で表しています)

りんごさんは、以下の一連の操作を、全ての人が会場から追い出されていなくなるまで繰り返します。

  • まだ追い出されていない人を 1 人選ぶ。
  • 選ばれた人は、目の前のマスが白で塗られている間、自分の向いている向きに 1 マス分進み、進んだ先のマスを自分の持っているペンキで塗る。目の前のマスが白で塗られていない場合、動作を終了する。
  • 動作を終了した人を会場から追い出す。

塗られ方の例

りんごさんが作ることのできる、最終的な盤面の塗られ方は何通りあるでしょうか。998244353 で割ったあまりを求めてください。

なお、 2 つの盤面の塗られ方が異なるとは、あるマスが存在し、そのマスの色が異なることを指します。

制約

  • 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

出力

最終的な盤面の塗られ方の総数を 998244353 で割ったあまりを出力せよ。

入力例 1

2 2
10
01
10
01

出力例 1

6

以下の 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

Score : 1600 points

Problem Statement

Ringo got interested in modern art. He decided to draw a big picture on the board with N+2 rows and M+2 columns of squares constructed in the venue of CODE FESTIVAL 2017, using some people.

The square at the (i+1)-th row and (j+1)-th column in the board is represented by the pair of integers (i,j). That is, the top-left square is (0,0), and the bottom-right square is (N+1,M+1). Initially, the squares (x,y) satisfying 1 \leq x \leq N and 1 \leq y \leq M are painted white, and the other (outermost) squares are painted black.

Ringo arranged people at some of the outermost squares, facing inward. More specifically, the arrangement of people is represented by four strings A, B, C and D, as follows:

  • For each row except the top and bottom, if the i-th character (1 \leq i \leq N) in A is 1, place a person facing right at the square (i,0); otherwise, do nothing.
  • For each row except the top and bottom, if the i-th character (1 \leq i \leq N) in B is 1, place a person facing left at the square (i,M+1); otherwise, do nothing.
  • For each column except the leftmost and rightmost, if the i-th character (1 \leq i \leq M) in C is 1, place a person facing down at the square (0,i); otherwise, do nothing.
  • For each column except the leftmost and rightmost, if the i-th character (1 \leq i \leq M) in D is 1, place a person facing up at the square (N+1,i); otherwise, do nothing.

Each person has a sufficient amount of non-white paint. No two people have paint of the same color.

An example of an arrangement of people (For convenience, black squares are displayed in gray)

Ringo repeats the following sequence of operations until all people are dismissed from the venue.

  • Select a person who is still in the venue.
  • The selected person repeats the following action while the square in front of him/her is white: move one square forward, and paint the square he/she enters with his/her paint. When the square in front of him/her is not white, he/she stops doing the action.
  • The person is now dismissed from the venue.

An example of a way the board is painted

How many different states of the board can Ringo obtain at the end of the process? Find the count modulo 998244353.

Two states of the board are considered different when there is a square painted in different colors.

Constraints

  • 1 \leq N,M \leq 10^5
  • |A|=|B|=N
  • |C|=|D|=M
  • A, B, C and D consist of 0 and 1.

Input

Input is given from Standard Input in the following format:

N M
A
B
C
D

Output

Print the number of the different states of the board Ringo can obtain at the end of the process, modulo 998244353.

Sample Input 1

2 2
10
01
10
01

Sample Output 1

6

There are six possible states as shown below.

Sample Input 2

2 2
11
11
11
11

Sample Output 2

32

Sample Input 3

3 4
111
111
1111
1111

Sample Output 3

1276

Sample Input 4

17 21
11001010101011101
11001010011010111
111010101110101111100
011010110110101000111

Sample Output 4

548356548

Be sure to find the count modulo 998244353.

Sample Input 5

3 4
000
101
1111
0010

Sample Output 5

21

Sample Input 6

9 13
111100001
010101011
0000000000000
1010111111101

Sample Output 6

177856

Sample Input 7

23 30
01010010101010010001110
11010100100100101010101
000101001001010010101010101101
101001000100101001010010101000

Sample Output 7

734524988