分数: 1400 点
问题陈述
在二维平面中,有一个正方形框架,其顶点位于坐标 (0,0), (N,0), (0,N),和 (N,N)。 框架由镜面玻璃制成。照射到框架边缘(但不是顶点)的光线将被反射,使得入射角等于反射角。 照射到框架顶点的光线将沿与其发出方向相反的方向反射。
我们将定义 路径 为网格点(具有整数坐标的点) (i,j) (0<i,j<N)严格在框架内,如下:
- 的路径 (i,j) 是从 (i,j) to (i-1,j-1), (i-1,j+1), (i+1,j-1),和 (i+1,j+1).
图:网格点路径示例
严格位于框架内的每个网格点都有一个灯泡。我们将为每个灯泡分配一个状态 - 开或关。整组灯泡的状态称为 美丽 如果可以通过重复以下操作关闭所有灯泡:
- 严格选择框架内的网格点,并切换其路径上所有灯泡的状态。
Takahashi 已设置某些灯泡的状态,但未设置其余灯泡的状态。
求设置剩余灯泡状态使整组灯泡状态美观的方法数,取模 998244353。
网格点处灯泡的状态 (i,j) 设置为 ON,如果 A_{i,j}=o,关闭如果 A_{i,j}=x,并取消设置,如果 A_{i,j}=?.
约束
- 2 \leq N \leq 1500
- A_{ij} is
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) 并切换灯泡的状态 在 (1,1), (1,3), (2,2), (3,1),和 (3,3).
示例输入 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