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，可以使用动态规划的方法求解。

---

原代码：

# 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，可以使用动态规划的方法求解。