题目描述

$N$ 人のすぬけ君が $1$ 列に並んでいます。 長さ $N$ の文字列 $S$ が与えられ、前から $i$ 人目のすぬけ君は $S$ の $i$ 文字目が 0 のとき赤いボールを $2$ つ、1 のとき赤いボールと青いボールを $1$ つずつ、2 のとき青いボールを $2$ つ持っています。

高橋君は最初、空の列を持っています。以下の操作を $2N$ 回繰り返してできる列としてありうるものの個数を $998244353$ で割った あまりを求めてください。

• ボールを $1$ つ以上持っているすぬけ君は全員同時に、自分が持っているボールの中から $1$ つを選び、前のすぬけ君に渡す。ただし、先頭のすぬけ君は、高橋君に渡す。
• 高橋君は、先頭のすぬけ君から受け取ったボールを、列の末尾に並べる。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$

输出格式

操作を $2N$ 回繰り返してできる列としてありうるものの個数を $998244353$ で割ったあまりを出力せよ。

题目大意

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

02

3

1210

55

12001021211100201020

543589959

提示

制約

• $1\ \leq\ |S|\ \leq\ 2000$
• $S$ は 0,1,2 からなる

整数 $N$ は入力では与えられず、文字列 $S$ の長さとして間接的に与えられることに注意せよ。

Sample Explanation 1

前から $i$ 個目に並んだボールの色が赤のとき r を、青のとき b を $i$ 文字目の文字とした長さ $2N$ の文字列で列を表すことにすれば、 rrbb,rbrb,rbbr が条件を満たします。