题目描述

现在有一个 $n \times n$ 的 $01$ 矩阵$^\dagger$ $A$。

一次对矩阵 $A$ 的操作被定义为：

• 对于所有 $1 \le i \le n,1 \le j \le n$，若 $A_{i-1,j}+A_{i+1,j} \ge 1$ 且 $A_{i,j-1}+A_{i,j+1} \ge 1$，则将 $A_{i,j}$ 改为 $1$，否则不变。

特别地，若 $i<1$ 或 $i>n$ 或 $j<1$ 或 $j>n$，则认为 $A_{i,j}=0$。

定义矩阵 $A$ 是好的，当且仅当对 $A$ 进行恰好 $10^{100}$ 次操作后，$A$ 中不存在 $0$。

给定一个 $n \times n$ 的 $01$ 矩阵 $B$。

已知此矩阵 $A$ 满足：

• 对于所有 $1 \le i,j \le n$，$A_{i,j} \le B_{i,j}$；
• $\sum_{i=1}^{n}\sum_{j=1}^{n} A_{i,j} \le n$；
• $A$ 是一个好矩阵。

问矩阵 $A$ 有多少种可能，答案对 $998244353$ 取模。

$\dagger$：指所有数均为 $0$ 或 $1$ 的矩阵。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 个整数为 $B_{i,j}$。

输出格式

仅一行一个整数，为答案对 $998244353$ 取模后的值。

样例

2
1 1
1 0

1

说明/提示

对于 $100\%$ 的数据：

• $1 \le n \le 150$；
• $B_{i,j} \in \{0,1\}$。

本题开启捆绑测试。

• Subtask #1（$5 \ \text{pts}$）：$n \le 5$。
• Subtask #2（$5 \ \text{pts}$）：$\sum_{i=1}^{n}\sum_{j=1}^{n} B_{i,j}=n$。
• Subtask #3（$10 \ \text{pts}$）：$n \le 8$。
• Subtask #4（$10 \ \text{pts}$）：$n \le 11$，$B_{i,j}=1$。
• Subtask #5（$5 \ \text{pts}$）：若 $|i-j| > 1$，则 $B_{i,j}=0$。
• Subtask #6（$20 \ \text{pts}$）：$n \le 18$。
• Subtask #7（$10 \ \text{pts}$）：$B_{i,j}=1$。
• Subtask #8（$10 \ \text{pts}$）：$n \le 40$。
• Subtask #9（$25 \ \text{pts}$）：无特殊限制。