分数: 900 点
问题陈述
有 N 潜弹排成一排。
给你一个字符串 S 长度 N.The i- 前面的第一个 Snuke 有两个红球,如果 i- 第一个字符 S is 0;一个红球和一个蓝球,如果 i- 第一个字符 S is 1;两个蓝色球,如果 i- 第一个字符 S is 2.
Takahashi 有一个最初为空的序列。重复以下过程后求他可能有的序列数 2N 次,模数 998244353:
- 每个同时拥有一个或多个球的 Snuke 选择一个球并将其交给他前面的 Snuke,如果他是该行中的第一个 Snuke,则将其交给高桥。
- 高桥接球并将其放在他的序列的末尾。
约束
- 1 \leq |S| \leq 2000
- S 包括
0,1和2.
请注意,整数 N 未在输入中直接给出;它作为字符串的长度间接给出 S.
输入
输入由标准输入按以下格式给出:
S
输出
重复该过程后,打印高桥可能拥有的可能序列的数量 2N 次,模数 998244353.
样本输入 1
02
示例输出 1
3
高桥可能有三个序列: rrbb, rbrb 和 rbbr,其中 r 和 b 分别代表红球和蓝球。
示例输入 2
1210
示例输出 2
55
示例输入 3
12001021211100201020
示例输出 3
543589959