AT_yahoo_procon2019_qual_f Pass

[problemUrl]: https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_f $ N $ 人のすぬけ君が $ 1 $ 列に並んでいます。 長さ $ N $ の文字列 $ S $ が与えられ、前から $ i $ 人目のすぬけ君は $ S $ の $ i $ 文字目が `0` のとき赤いボールを $ 2 $ つ、`1` のとき赤いボールと青いボールを $ 1 $ つずつ、`2` のとき青いボールを $ 2 $ つ持っています。 高橋君は最初、空の列を持っています。以下の操作を $ 2N $ 回繰り返してできる列としてありうるものの個数を $ 998244353 $ で割った あまりを求めてください。 - ボールを $ 1 $ つ以上持っているすぬけ君は全員同時に、自分が持っているボールの中から $ 1 $ つを選び、前のすぬけ君に渡す。ただし、先頭のすぬけ君は、高橋君に渡す。 - 高橋君は、先頭のすぬけ君から受け取ったボールを、列の末尾に並べる。

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

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

### 制約 - $ 1\ \leq\ |S|\ \leq\ 2000 $ - $ S $ は `0`,`1`,`2` からなる 整数 $ N $ は入力では与えられず、文字列 $ S $ の長さとして間接的に与えられることに注意せよ。 ### Sample Explanation 1 前から $ i $ 個目に並んだボールの色が赤のとき `r` を、青のとき `b` を $ i $ 文字目の文字とした長さ $ 2N $ の文字列で列を表すことにすれば、 `rrbb`,`rbrb`,`rbbr` が条件を満たします。