Modern Painting

[problemUrl]: https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_e 現代美術に興味を持ったりんごさんは、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 $ つの盤面の塗られ方が異なるとは、あるマスが存在し、そのマスの色が異なることを指します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A $ $ B $ $ C $ $ D $

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

2 2
10
01
10
01

6

2 2
11
11
11
11

32

3 4
111
111
1111
1111

1276

17 21
11001010101011101
11001010011010111
111010101110101111100
011010110110101000111

548356548

3 4
000
101
1111
0010

21

9 13
111100001
010101011
0000000000000
1010111111101

177856

23 30
01010010101010010001110
11010100100100101010101
000101001001010010101010101101
101001000100101001010010101000

734524988

### 制約 - $ 1\ \leq\ N,M\ \leq\ 10^5 $ - $ |A|=|B|=N $ - $ |C|=|D|=M $ - $ A,B,C,D $ は `0` と `1` からなる ### Sample Explanation 1 以下の $ 6 $ 通りの塗られ方があります。 !\[\](https://atcoder.jp/img/code-festival-2017-quala/1dd467cdff8a517c9555abfca0915e2e.png) ### Sample Explanation 4 $ 998244353 $ で割ったあまりを求めるのを忘れないようにしてください。