配点 : $1400$ 点

問題文

二次元平面上に正方形の形をした枠があり、その $4$ 頂点の座標は $(0,0)$, $(N,0)$, $(0,N)$, $(N,N)$ です。 この枠は鏡でできており、枠の辺（頂点を除く）に光が当たると入射角と反射角が等しくなるように光が反射します。 ただし、頂点に光が当たると、光は入射してきた向きと逆向きに反射します。

ここで、枠の内部にある格子点 $(i,j)$ ($0) に対応するラインを次のように定義します。

• $(i,j)$ から $(i-1,j-1)$, $(i-1,j+1)$, $(i+1,j-1)$, $(i+1,j+1)$ への $4$ 方向に光を発したときに、 光が通る軌跡を $(i,j)$ のラインとする。

図: 格子点に対応するラインの例

枠の内部にある各格子点上には電球が $1$ つずつあります。それぞれの電球に対してonとoffのいずれかの状態を定めたとき、 以下の操作を繰り返して全ての電球をoffにできるならば、その電球の状態をきれいと呼ぶことにします。

• 枠の内部にある格子点を $1$ つ選び、そのライン上にある全ての電球のonとoffを切り替える。

高橋君はいくつかの電球のonとoffの状態を決めましたが、いくつかの電球の状態はまだ決めていません。 それらのonとoffを定める方法であって、電球の状態がきれいになるような方法の数を $998244353$ で割ったあまりを求めてください。 格子点 $(i,j)$ にある電球は $A_{i,j}=$o のときon、$A_{i,j}=$x のときoffであり、$A_{i,j}=$? のとき状態がまだ決まっていません。

制約

• $2 \leq N \leq 1500$
• $A_{i,j}$ は o, x, ? のいずれか

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_{1,1}...A_{1,N-1}$

$:$

$A_{N-1,1}...A_{N-1,N-1}$

出力

答えを出力せよ。

4
o?o
???
?x?

1

以下のように各電球の状態を決めれば、電球の状態はきれいとなります。

oxo
xox
oxo

例えば $(1,1)$ のライン上にある電球のonとoffを切り替えると、 $(1,1)$, $(1,3)$, $(2,2)$, $(3,1)$, $(3,3)$ にある電球のonとoffが切り替わるので、 すべての電球がoffになります。

5
o?o?
????
o?x?
????

0

6
?o???
????o
??x??
o????
???o?

32

9
????o??x
?????x??
??o?o???
?o?x????
???????x
x?o?o???
????????
x?????x?

4