問題文

グリッド $A, B$ があり、いずれも縦 $H$ マス 横 $W$ マスの、計 $HW$ マスからなります。
$A, B$ の上から $i \scriptsize \; (1 \leq i \leq H)$ 行目、左から $j \scriptsize \; (1 \leq j \leq W)$ 行目のマスには、それぞれ整数 $A_{i, j}, B_{i, j}$ が書かれています。

これらのグリッドの $1$ つ以上のマスに色を塗ります。

よい塗り方は、以下をすべて満たします：

• $A, B$ いずれについても、任意の行に対して、その行は高々 $1$ つのマスが塗られている。
• $A, B$ いずれについても、任意の列に対して、その列は高々 $1$ つのマスが塗られている。
• $A$ の「色の塗られたマスが存在する行の番号」の集合と、$B$ の「色の塗られたマスが存在する行の番号」の集合は等しい。
• $A$ の「色の塗られたマスが存在する列の番号」の集合と、$B$ の「色の塗られたマスが存在する列の番号」の集合は等しい。

ここで、色の塗られたグリッド $X$ について、$X$ のスコア $f(X)$ は次のように計算されます：

1. 色の塗られたマスすべてについて、自由な順に以下の操作を $1$ 回ずつ行う (結果は順番に依らない)：
   • そのマスより (真に) 右 かつ (真に) 上 にあるようなすべてのマスについて、そのマスに書かれている数 $x$ を $-x$ で置き換える。
2. その後、色の塗られたマスすべてをわたる、そのマスに書かれた数の総積を求め、それを $f(X)$ とする。

よい塗り方すべてをわたる、$f(A) \times f(B)$ の総和を求めてください。
ただし、答えの絶対値は大きくなる場合があるので、$998244353$ で割ったあまりを出力してください。

なお、$A$ の「色の塗られたマス」の集合が異なり、かつ または (2024.07.26 21:41 修正) $B$ の「色の塗られたマス」の集合が異なるとき、またそのときに限り、塗り方は異なります。

入力

入力は、以下の形式で標準入力より与えられる：

$H \enspace W$
$A_{1, 1} \enspace A_{1, 2} \enspace \dots \enspace A_{1, W}$
$A_{2, 1} \enspace A_{2, 2} \enspace \dots \enspace A_{2, W}$
$\vdots$
$A_{H, 1} \enspace A_{H, 2} \enspace \dots \enspace A_{H, W}$
$B_{1, 1} \enspace B_{1, 2} \enspace \dots \enspace B_{1, W}$
$B_{2, 1} \enspace B_{2, 2} \enspace \dots \enspace B_{2, W}$
$\vdots$
$B_{H, 1} \enspace B_{H, 2} \enspace \dots \enspace B_{H, W}$

出力

答えを求め、$998244353$ で割ったあまりを標準出力へ一行に出力せよ。
ただし「$x$ を $998244353$ で割ったあまり」とは、$x = 998244353 \times q + r$ なる整数 $q$ が存在し、かつ $0 \leq r < 998244353$ をみたすような唯一の整数 $r$ である。

制約

• $1 \leq H \leq 100$
• $1 \leq W \leq 2000$
• $0 \leq A_{i, j} < 998244353 \scriptsize \; (1 \leq i \leq H \land 1 \leq j \leq W)$
• $0 \leq B_{i, j} < 998244353 \scriptsize \; (1 \leq i \leq H \land 1 \leq j \leq W)$
• 入力はすべて整数

サンプル

2 3
1 2 3
4 5 6
7 8 9
10 11 12

271