← 返回题目列表

Codeforces · 1767/C

C. 计算二进制字符串

中文机器翻译题面 查看原题

给你一个整数$$$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。