统计二进制串

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定长度 $n$。对每个 $1\le i\le j\le n$ 给出 $a_{i,j}$：值为 $1$ 时要求二进制串的区间 $[i,j]$ 全部相同；值为 $2$ 时要求区间内至少出现两种字符；值为 $0$ 时没有限制。求满足全部条件的二进制串数量，对 $998244353$ 取模。

输入格式

第一行包含 $n$。随后第 $i$ 行包含 $a_{i,i},a_{i,i+1},\ldots,a_{i,n}$。

输出格式

输出合法字符串数量。

样例输入 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

数据范围

• $2\le n\le100$；
• $0\le a_{i,j}\le2$。