Problem Description

In a two-dimensional plane, there is a square frame with its four vertices at coordinates $(0,0)$, $(N,0)$, $(0,N)$, and $(N,N)$. This frame is made of mirrors, and when light hits the sides of the frame (excluding the vertices), it reflects such that the angle of incidence equals the angle of reflection. However, if light hits a vertex, it reflects back in the opposite direction of the incident light.

Now, we define a line corresponding to a grid point $(i,j)$ (where $0 < i, j < N$) as follows:

• The trajectory of light emitted from $(i,j)$ in the four directions towards $(i-1,j-1)$, $(i-1,j+1)$, $(i+1,j-1)$, and $(i+1,j+1)$ constitutes the line of $(i,j)$.

There is one light bulb at each grid point inside the frame. When the state of each bulb (either on or off) is determined, if all bulbs can be turned off by repeatedly performing the following operation, we call the state of the bulbs clean:

• Select a grid point inside the frame and toggle the state of all bulbs on the corresponding line.

Takahashi has determined the states of some bulbs, but the states of some others are still undecided. Determine the number of ways to set the states of these bulbs such that the state of the bulbs is clean, modulo $998244353$. The bulb at grid point $(i,j)$ is on if $A_{i,j} =$ o, off if $A_{i,j} =$ x, and undecided if $A_{i,j} =$ ?.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

4
o?o
???
?x?

Sample Output #1

1

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

Notes/Hints

Constraints

• $ 2 ≦ N ≦ 1500 $
• $ A_{i,j} $ is one of o, x, ?

Sample Explanation 1

If the states of the bulbs are determined as follows, the state of the bulbs is clean:

oxo
xox
oxo

For example, toggling the states of the bulbs on the line of $(1,1)$ will switch the states of the bulbs at $(1,1)$, $(1,3)$, $(2,2)$, $(3,1)$, and $(3,3)$, turning all bulbs off.

见题面 Input 部分

见题面 Output 部分