問題文

$H$ 行 $W$ 列のマス目があります。上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と呼ぶことにします。

マス目の各マスには整数が書かれており、マス $(i,j)$ に書かれている整数は $A_{i,j}$ です。

マス目のマスを $1$ つ以上選び、選んだマスそれぞれに印を付けます。印の付け方のスコアを、印を付けたマスたちに書かれている整数の最大値と定めます。

また、印の付け方が以下の条件を満たす場合、その印の付け方を良い印の付け方と呼ぶことにします。

• マス目の任意の縦 $2$ 行、横 $2$ 列の正方形領域について、その領域に含まれる $4$ つのマスのうち印が付けられているマスは偶数個である。

印の付け方は全部で $2^{H×W}-1$ 通りあります。そのうち良い印の付け方全てについてスコアを計算し、その総和を $998244353$ で割った余りを求めて下さい。

入力

$H\ W$
$A_{1,1}\ A_{1,2} \ .. \ A_{1,W}$
$A_{2,1}\ A_{2,2} \ .. \ A_{2,W}$
:
$A_{H,1}\ A_{H,2} \ .. \ A_{H,W}$

• $2\le H,W\le 1000$
• $1\le A_{i,j}\le 998244352$
• 入力はすべて整数

出力

全ての良い印の付け方のスコアの総和を $998244353$ で割った余りを出力してください。

サンプル

サンプル1

入力サンプルをコピー

入力

2 2
3 3
1 4

出力

25

良い印の付け方は以下の $7$ 通りです。(印が付いたマスの整数の最大値を太字にしています)

よって、答えは $3+4+4+3+4+3+4=25$ です。

3 3
1 2 3
4 5 6
7 8 9

251