CF1767C.Count Binary Strings

You are given an integer $n$. You have to calculate the number of binary (consisting of characters 0 and/or 1) strings $s$ meeting the following constraints.

For every pair of integers $(i, j)$ such that $1 \le i \le j \le n$, an integer $a_{i,j}$ is given. It imposes the following constraint on the string $s_i s_{i+1} s_{i+2} \dots s_j$:

• if $a_{i,j} = 1$, all characters in $s_i s_{i+1} s_{i+2} \dots s_j$ should be the same;
• if $a_{i,j} = 2$, there should be at least two different characters in $s_i s_{i+1} s_{i+2} \dots s_j$;
• if $a_{i,j} = 0$, there are no additional constraints on the string $s_i s_{i+1} s_{i+2} \dots s_j$.

Count the number of binary strings $s$ of length $n$ meeting the aforementioned constraints. Since the answer can be large, print it modulo $998244353$.

给你一个整数 $n$。你需要计算满足以下约束条件的二进制字符串（仅由字符 0 和/或 1 组成）$s$ 的数量。

对每一对满足 $1 \le i \le j \le n$ 的整数 $(i, j)$，给定一个整数 $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$ 取模的结果。

The first line contains one integer $n$ ($2 \le n \le 100$).

Then $n$ lines follow. The $i$-th of them contains $n-i+1$ integers $a_{i,i}, a_{i,i+1}, a_{i,i+2}, \dots, a_{i,n}$ ($0 \le a_{i,j} \le 2$).

第一行包含一个整数 $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$）。

Print one integer — the number of strings meeting the constraints, taken modulo $998244353$.

输出一个整数——满足约束条件的字符串数量，对 $998244353$ 取模。

In the first example, the strings meeting the constraints are 001, 010, 011, 100, 101, 110.

In the second example, the strings meeting the constraints are 001, 110.

在第一个例子中，满足约束条件的字符串有 001、010、011、100、101、110。

在第二个例子中，满足约束条件的字符串有 001、110。