Score : 900 points
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:
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 is given from Standard Input in the following format:
S
Print the number of the possible sequences Takahashi may have after repeating the procedure 2N times, modulo 998244353.
02
3
There are three sequences that Takahashi may have: rrbb
, rbrb
and rbbr
, where r
and b
stand for red and blue balls, respectively.
1210
55
12001021211100201020
543589959