Little Cyan Fish 有一个 $n \times n$ 的矩阵。每一行和每一列的左侧和顶端各有一根棍子。令 $x_i$ 表示第 $i$ 行左侧棍子的长度，$y_i$ 表示第 $i$ 列顶端棍子的长度，其中 $0 \le x_i, y_i \le n$ 且均为整数。此外，这些棍子不能相交，这意味着不存在 $i, j \in [1, n]$ 使得 $x_i \ge j$ 且 $y_j \ge i$ 同时成立。

Little Cyan Fish 定义矩阵 $A$ 如下： * 对于每个 $i, j \in [1, n]$，如果 $x_i \ge j$ 或 $y_j \ge i$，则 $A_{i,j} = 1$；否则 $A_{i,j} = 0$。

给定一个包含 $0, 1$ 和 $?$ 的 $n \times n$ 矩阵 $M$，你需要确定有多少种不同的矩阵可以通过将每个 $?$ 替换为 $0$ 或 $1$ 来形成，使得至少存在一组棍子 $\{x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_n\}$ 可以得到该矩阵。由于答案可能很大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3\,000$)。 接下来的 $n$ 行描述了矩阵 $M$。每一行包含一个长度为 $n$ 的字符串，由 “0”、“1” 和 “?” 组成，表示该矩阵。

输出格式

输出一行，包含一个整数，表示答案。

样例

样例输入 1

2
??
??

样例输出 1

14

样例输入 2

5
??1??
?1??0
??0??
???1?
??1??

样例输出 2

3144

样例输入 3

10
0000000000
??????????
??????????
??????????
??????????
??????????
??????????
??????????
??????????
??????????

样例输出 3

361458985