Eva 喜欢绘画。今天她正在使用一个 $n \times n$ 单位格的方形画布。每个单元格要么被涂成白色，要么被涂成黑色，要么是空的（即未涂色）。

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

每个三角形都是一件艺术品，Eva 希望它们能与画作的其余部分容易区分。为了实现这一点，任意两个黑色三角形不得共享公共边，且任意黑色三角形不得与黑色正方形共享公共边。注意，两个黑色正方形允许共享公共边。

请帮助 Eva 计算完成画作的方法总数。由于结果可能很大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $n$ —— 画布的边长 ($1 \le n \le 1000$)。

接下来的 $n$ 行从上到下描述了画布。其中第 $i$ 行包含 $n$ 个字符 $s_{i,1}, s_{i,2}, \dots, s_{i,n}$。如果 $s_{i,j} = \text{‘.’}$，则画布第 $i$ 行第 $j$ 列的单元格被涂成白色。如果 $s_{i,j} = \text{‘\#’}$，则该单元格被涂成黑色。如果 $s_{i,j} = \text{‘?’}$，则该单元格为空。

输出格式

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

样例

样例输入 1

2
.?
?#

样例输出 1

4

样例输入 2

3
#??
#??
?##

样例输出 2

1

样例输入 3

3
.#.
#?#
.#.

样例输出 3

0

说明

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

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

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