F - Pass Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

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

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

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

制約

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

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

入力

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

S

出力

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

入力例 1

02

出力例 1

3

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

入力例 2

1210

出力例 2

55

入力例 3

12001021211100201020

出力例 3

543589959

Score : 900 points

Problem Statement

There are N Snukes lining up in a row. You are given a string S of length N. The i-th Snuke from the front has two red balls if the i-th character in S is 0; one red ball and one blue ball if the i-th character in S is 1; two blue balls if the i-th character in S is 2.

Takahashi has a sequence that is initially empty. Find the number of the possible sequences he may have after repeating the following procedure 2N times, modulo 998244353:

  • Each Snuke who has one or more balls simultaneously chooses one of his balls and hand it to the Snuke in front of him, or hand it to Takahashi if he is the first Snuke in the row.
  • Takahashi receives the ball and put it to the end of his sequence.

Constraints

  • 1 \leq |S| \leq 2000
  • S consists of 0,1 and 2.

Note that the integer N is not directly given in input; it is given indirectly as the length of the string S.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of the possible sequences Takahashi may have after repeating the procedure 2N times, modulo 998244353.

Sample Input 1

02

Sample Output 1

3

There are three sequences that Takahashi may have: rrbb, rbrb and rbbr, where r and b stand for red and blue balls, respectively.

Sample Input 2

1210

Sample Output 2

55

Sample Input 3

12001021211100201020

Sample Output 3

543589959