← 返回题目列表

AtCoder · nikkei2019_2_qual_f

F. 镜框

中文机器翻译题面 查看原题

分数: 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