给你一个整数$$$n$$$。您必须计算满足以下约束的二进制(由字符 0 和/或 1 组成)字符串 $$$s$$$ 的数量。
对于每对整数 $$$(i, j)$$$ 使得 $$$1 \le i \le j \le n$$$,给出一个整数 $$$a_{i,j}$$$。它对字符串 $$$s_i s_{i+1} s_{i+2} \dots s_j$$$ 施加以下约束:
- 如果 $$$a_{i,j} = 1$$$,则 $$$s_i s_{i+1} s_{i+2} \dots s_j$$$ 中的所有字符应该相同;
- 如果 $$$a_{i,j} = 2$$$,$$$s_i s_{i+1} s_{i+2} \dots s_j$$$ 中至少应该有两个不同的字符;
- 如果 $$$a_{i,j} = 0$$$,则字符串 $$$s_i s_{i+1} s_{i+2} \dots s_j$$$ 没有其他约束。
计算长度为 $$$n$$$ 且满足上述约束的二进制字符串 $$$s$$$ 的数量。由于答案可能很大,因此打印它对 $$$998244353$$$ 取模。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$)。
然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含 $$$n-i+1$$$ 整数 $$$a_{i,i}、a_{i,i+1}、a_{i,i+2}、\dots、a_{i,n}$$$ ($$$0 \le a_{i,j} \le 2$$$)。
输出
打印一个整数 — 满足约束条件的字符串数量,以 $$$998244353$$$ 为模。
示例
输入 #1
3 1 0 2 1 0 1
输出 #1
6
输入 #2
3 1 1 2 1 0 1
输出 #2
2
输入 #3
3 1 2 1 1 0 1
输出 #3
0
输入#4
3 2 0 2 0 1 1
输出#4
0
注意
在第一个示例中,满足约束的字符串是 001、010、011、100、101、110。
在第二个示例中,满足约束的字符串是 001、110。