Description

Eva 喜欢绘画。今天她正在用一个 $n \times n$ 的正方形画布进行创作。每个单元格可能被涂成白色、黑色，或者为空——即未被涂色。

Eva 准备在每个空单元格内画一个黑色三角形。她希望每个三角形都是直角三角形，且面积为 $\frac{1}{2}$ 个单元格。因此，在一个单元格内画三角形有四种方式：

每个三角形都是一件艺术品，Eva 希望它们能与画布上的其它部分容易区分。为此，任意两个黑色三角形不能有公共边，且任意黑色三角形也不能与黑色单元格有公共边。注意，两个黑色单元格之间可以有公共边。

请你帮助 Eva 计算完成画作的方案数。由于答案可能很大，请对 $998\,244\,353$ 取模后输出。

Input Format

第一行包含一个整数 $n$，表示画布的边长（$1 \le n \le 1000$）。

接下来的 $n$ 行描述画布的状态，从上到下依次给出。第 $i$ 行包含 $n$ 个字符 $s_{i, 1}, s_{i, 2}, \ldots, s_{i, n}$。如果 $s_{i, j} = \texttt{.}$，表示第 $i$ 行第 $j$ 列的单元格被涂成白色；如果 $s_{i, j} = \texttt{\#}$，表示该单元格被涂成黑色；如果 $s_{i, j} = \texttt{?}$，表示该单元格为空。

Output Format

输出一个整数，表示完成 Eva 画作的方案数，对 $998\,244\,353$ 取模。

2
.?
?#

4

3
#??
#??
?##

1

3
.#.
#?#
.#.

0

Hint

在第一个样例测试中，共有 $4$ 种完成画作的方式，如下图所示：

在第二个样例测试中，只有一种完成画作的方式：

在第三个样例测试中，无论 Eva 如何在中心单元格画三角形，它都会与黑色单元格有两条公共边。

由 ChatGPT 4.1 翻译