Problem Description

There are $ N $ Snuke-kun lined up in a row. Given a string $ S $ of length $ N $, the $ i $-th Snuke-kun from the front has 2 red balls if the $ i $-th character of $ S $ is 0, 1 red ball and 1 blue ball if it is 1, and 2 blue balls if it is 2.

Takahashi initially has an empty sequence. Find the number of possible sequences that can be formed after repeating the following operation $ 2N $ times, modulo $ 998244353 $.

• All Snuke-kun who have at least one ball simultaneously choose one of their balls and pass it to the previous Snuke-kun. However, the first Snuke-kun passes the ball to Takahashi.
• Takahashi appends the ball received from the first Snuke-kun to the end of his sequence.

Input Format

The input is given from the standard input in the following format:

$ S $

Output Format

Output the number of possible sequences that can be formed after repeating the operation $ 2N $ times, modulo $ 998244353 $.

Sample Input and Output

Sample Input #1

02

Sample Output #1

3

Sample Input #2

1210

Sample Output #2

55

Sample Input #3

12001021211100201020

Sample Output #3

543589959

Notes/Hints

Constraints

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

Note that the integer $ N $ is not given directly in the input but is implied by the length of the string $ S $.

Sample Explanation 1

If we represent the sequence as a string of length $ 2N $ where r denotes a red ball and b denotes a blue ball in the $ i $-th position from the front, then rrbb, rbrb, and rbbr satisfy the conditions.

见题面 Input 部分

见题面 Output 部分