Problem Description

Ringo, having developed an interest in modern art, decided to create a painting using an $N+2$ by $M+2$ board and several people at the CODE FESTIVAL 2017 venue.

The square at the $i+1$th row from the top and the $j+1$th column from the left is represented by the pair of integers [MATH4][MATH5][MATH6]$ satisfying $1 \leq x \leq N, 1 \leq y \leq M$ are painted white, while the rest (the outer squares) are painted black.

Ringo placed some people facing inward on some of the outer squares of the board. More specifically, the placement information is represented by four strings $A, B, C, D$, and the placement is done as follows:

• For each row except the ends, if the $i$th (1 \leq i \leq N) character of $A$ is 1, place one person facing right at square $(i,0)$. Otherwise, do nothing.
• For each row except the ends, if the $i$th (1 \leq i \leq N) character of $B$ is 1, place one person facing left at square $(i,M+1)$. Otherwise, do nothing.
• For each column except the ends, if the $i$th (1 \leq i \leq M) character of $C$ is 1, place one person facing down at square $(0,i)$. Otherwise, do nothing.
• For each column except the ends, if the $i$th (1 \leq i \leq M) character of $D$ is 1, place one person facing up at square $(N+1,i)$. Otherwise, do nothing.

Each person has a sufficient amount of non-white paint, and the color of paint each person has is unique.

Ringo repeats the following sequence of operations until all people are removed from the venue:

• Select one person who has not been removed yet.
• The selected person moves one square in the direction they are facing and paints the square with their paint as long as the square in front of them is white. If the square in front of them is not white, they stop.
• Remove the person who stopped from the venue.

How many different final painted states of the board can Ringo create? Find the answer modulo $998244353$.

Two painted states of the board are considered different if there exists a square whose color is different.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the total number of possible final painted states of the board modulo $998244353$.

Sample Input and Output

Sample Input #1

2 2
10
01
10
01

Sample Output #1

6

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

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

Notes/Hints

Constraints

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

见题面 Input 部分

见题面 Output 部分