{"problem":{"name":"Mirror Frame","description":{"content":"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 ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"nikkei2019_2_qual_f"},"statements":[{"statement_type":"Markdown","content":"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.\nWe 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:\n\n*   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)$.\n\n![image](https://img.atcoder.jp/nikkei2019-2-qual/f82200c30253b6e06c6043a2c7668735.png)Figure: an example of a path for a grid point\n\nThere 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:\n\n*   Choose a grid point strictly within the frame, and switch the states of all the bulbs on its path.\n\nTakahashi 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}=$`?`.\n\n## Constraints\n\n*   $2 \\leq N \\leq 1500$\n*   $A_{ij}$ is `o`, `x`, or `?`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_{1,1}...A_{1,N-1}$\n$:$\n$A_{N-1,1}...A_{N-1,N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"nikkei2019_2_qual_f","tags":[],"sample_group":[["4\no?o\n???\n?x?","1\n\nThe state of the whole set of bulbs will be beautiful if we set the state of each bulb as follows:\n\noxo\nxox\noxo\n\nWe 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)$."],["5\no?o?\n????\no?x?\n????","0"],["6\n?o???\n????o\n??x??\no????\n???o?","32"],["9\n????o??x\n?????x??\n??o?o???\n?o?x????\n???????x\nx?o?o???\n????????\nx?????x?","4"]],"created_at":"2026-03-03 11:01:13"}}