F - Mirror Frame Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1400 点

問題文

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

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

  • (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 ≦ N ≦ 1500
  • A_{i,j} は o, x, ? のいずれか

入力

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

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

出力

答えを出力せよ。

入力例 1

4
o?o
???
?x?

出力例 1

1

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

oxo
xox
oxo

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

入力例 2

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

出力例 2

0

入力例 3

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

出力例 3

32

入力例 4

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

出力例 4

4

Score : 1400 points

Problem Statement

In a two-dimensional plane, there is a square frame whose vertices are at coordinates (0,0), (N,0), (0,N), and (N,N). The frame is made of mirror glass. A ray of light striking an edge of the frame (but not a vertex) will be reflected so that the angle of incidence is equal to the angle of reflection. A ray of light striking a vertex of the frame will be reflected in the direction opposite to the direction it is coming from.

We will define the path for a grid point (a point with integer coordinates) (i,j) (0<i,j<N) strictly within the frame, as follows:

  • The path for (i,j) is the union of the trajectories of four rays of light emitted from (i,j) to (i-1,j-1), (i-1,j+1), (i+1,j-1), and (i+1,j+1).

Figure: an example of a path for a grid point

There is a light bulb at each grid point strictly within the frame. We will assign a state - ON or OFF - to each bulb. The state of the whole set of bulbs are called beautiful if it is possible to turn OFF all the bulbs by repeating the following operation:

  • Choose a grid point strictly within the frame, and switch the states of all the bulbs on its path.

Takahashi has set the states of some of the bulbs, but not for the remaining bulbs. Find the number of ways to set the states of the remaining bulbs so that the state of the whole set of bulbs is beautiful, modulo 998244353. The state of the bulb at the grid point (i,j) is set to be ON if A_{i,j}=o, OFF if A_{i,j}=x, and unset if A_{i,j}=?.

Constraints

  • 2 \leq N \leq 1500
  • A_{ij} is o, x, or ?.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

4
o?o
???
?x?

Sample Output 1

1

The state of the whole set of bulbs will be beautiful if we set the state of each bulb as follows:

oxo
xox
oxo

We can turn OFF all the bulbs by, for example, choosing the point (1, 1) and switching the states of the bulbs at (1,1), (1,3), (2,2), (3,1), and (3,3).

Sample Input 2

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

Sample Output 2

0

Sample Input 3

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

Sample Output 3

32

Sample Input 4

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

Sample Output 4

4