AT_yahoo_procon2019_qual_f Pass

# Pass 有 $N$ 个人排成一列。给定一个长度为 $N$ 的字符串 $S$，第 $i$ 个人手中的球的数量如下： - 当 $S_i=0$ 时，这个人手中有两个红球； - 当 $S_i=1$ 时，这个人手中有一个红球和一个蓝球； - 当 $S_i=2$ 时，这个人手中有两个蓝球。 一开始，高桥君手中没有球，他要进行 $2N$ 次操作，每次操作如下： - 如果有人手中有球，则所有人同时选择一个自己手中的球，将其交给前面的人（第一个人将球交给高桥君）； - 高桥君将收到的球放到队列的末尾。 请计算出高桥君可以得到的所有队列的数量，答案对 $998244353$ 取模。

> $S$

输出高桥君可以得到的所有队列的数量，答案对 $998244353$ 取模。 ## 样例 #1 ### 样例输入 #1 ``` 02 ``` ### 样例输出 #1 ``` 3 ``` ## 样例 #2 ### 样例输入 #2 ``` 1210 ``` ### 样例输出 #2 ``` 55 ``` ## 样例 #3 ### 样例输入 #3 ``` 12001021211100201020 ``` ### 样例输出 #3 ``` 543589959 ```

- $1\leq |S|\leq 2000$ - $S$ 仅包含数字 $0,1,2$。 注意：输入中不会给出 $N$，而是通过字符串 $S$ 的长度间接给出。 ### 样例解释 可以将队列看作一个长度为 $2N$ 的字符串，第 $i$ 个字符表示第 $i$ 个人交给高桥君的球的颜色，红色用字母 `r` 表示，蓝色用字母 `b` 表示。例如，字符串 `rrbb` 表示高桥君先收到两个红球，然后收到两个蓝球。 对于样例 #1，可以构造出三个合法的队列：`rrbb`，`rbrb` 和 `rbbr`。 对于样例 #2 和样例 #3，可以使用动态规划的方法求解。