Problem:
 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

Solution (Python):
from itertools import accumulate
import sys
input = sys.stdin.readline

mod = 998244353
S = list(map(int, input().rstrip()))
N = len(S)
front = [0] * N
back = [0] * N
cum = list(accumulate(S))
for i in range(N-1):
    front[i+1] = max(front[i], i + 1 - cum[i])
    back[i+1] = max(back[i], cum[i] - (i + 1))
cnt = cum[-1]
dp = [1] * (2 * N - cnt + 1)
for i in range(N - 1, -1, -1):
    for c in range(S[i]):
        f = front[i]
        b = 2 * N - cum[-1]
        for j in range(N):
            if back[j] == cnt:
                b = 2 * j - cum[j-1]
                break
        for j in range(b - 1, f - 1, -1):
            dp[j] = (dp[j] + dp[j+1]) % mod
        for j in range(f - 1, -1, -1):
            dp[j] = dp[j+1]
        cnt -= 1
print(dp[0])

Solution (Python):
S=input()
N=len(S)
mod= 998244353

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

R=0
B=0

RB=[[0,0]]*N

for i in range(N):
    s=S[i]
    if s=="0":
        R+=2
    elif s=="1":
        R+=1
        B+=1
    else:
        B+=2
    RB[i]=[R,B]

DP=[0]*(R+1)
DP[0]=1

for i in range(N):
    NDP=[0]*(R+1)
    red,blue=RB[i]
    for r in range(R+1):
        if DP[r]==0:
            continue
        if r+1<=red:
            NDP[r+1]+=DP[r]
        if i-r+1<=blue:
            NDP[r]+=DP[r]
    DP=NDP


ANS=0
for r in range(R+1):
    red=R-r
    blue=B-(N-r)

    ANS=ANS+DP[r]*Combi(red+blue,blue)
    ANS%=mod
print(ANS)

Solution (Python):
S=input()
N=len(S)
mod= 998244353

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

R=0
B=0

RB=[[0,0]]*N

for i in range(N):
    s=S[i]
    if s=="0":
        R+=2
    elif s=="1":
        R+=1
        B+=1
    else:
        B+=2
    RB[i]=[R,B]

DP=[0]*(R+1)
DP[0]=1

for i in range(N):
    NDP=[0]*(R+1)
    red,blue=RB[i]
    for r in range(R+1):
        if DP[r]==0:
            continue
        if r+1<=red:
            NDP[r+1]+=DP[r]
        if i-r+1<=blue:
            NDP[r]+=DP[r]
    DP=NDP


ANS=0
for r in range(R+1):
    red=R-r
    blue=B-(N-r)

    ANS=ANS+DP[r]*Combi(red+blue,blue)
    ANS%=mod
print(ANS)

Solution (Python):
S = input()
n = len(S)
mod = 998244353


dp = [[0] * (2 * n + 1) for i in range(2 * n + 1)]
dp[0][0] = 1
now = 0
for i, s in enumerate(S):
    now += int(s)
    for j in range(i+1):
        dp[i + 1][j] += ((2 * (i + 1) - now - (i - j)) > 0) * dp[i][j]
        dp[i + 1][j + 1] += ((now - j) > 0) * dp[i][j]
        dp[i + 1][j] %= mod
        dp[i + 1][j + 1] %= mod
ans = 0
for i in range(n, 2 * n):
    for j in range(i+1):
        dp[i + 1][j] += ((2 * n - now - (i - j)) > 0) * dp[i][j]
        dp[i + 1][j + 1] += ((now - j) > 0) * dp[i][j]
        dp[i + 1][j] %= mod
        dp[i + 1][j + 1] %= mod
print(sum(dp[2*n])%mod)

Solution (Python):
S=input()
N=len(S)
C=[0]
for i in range(N):
  C.append(C[i]+int(S[i]))
for i in range(N):
  C.append(C[N])
B=C[N]
DP=[[0]*(B+1) for i in range(2*N+1)]
DP[0][0]=1
mod=998244353
for i in range(2*N):
  for j in range(B+1):
    if 2*min(i+1,N)-C[i+1]>=i+1-j:
      DP[i+1][j]=(DP[i+1][j]+DP[i][j])%mod
    if j<C[i+1]:
      DP[i+1][j+1]=DP[i][j]
print(DP[2*N][B])

Solution (Python):
s = input()
n = len(s)
mod = 998244353

rb_use = [[0]*(2*n+1)  for _ in range(2)]
r = 0
b = 0
for i in range(n):
    if(s[i]=='0'):
        r += 2
    elif(s[i]=='1'):
        r += 1
        b += 1
    else:
        b += 2
    rb_use[0][i+1] = rb_use[0][i]
    rb_use[1][i+1] = rb_use[1][i]
    if(r>0):
        rb_use[0][i+1] += 1
        r -= 1
    if(b>0):
        rb_use[1][i+1] += 1
        b -= 1

for i in range(n,2*n):
    rb_use[0][i+1] = rb_use[0][i]
    rb_use[1][i+1] = rb_use[1][i]
    if(r>0):
        rb_use[0][i+1] += 1
        r -= 1
    if(b>0):
        rb_use[1][i+1] += 1
        b -= 1

r_max = rb_use[0][-1]
b_max = rb_use[1][-1]

dp = [[0] * (b_max+1) for _ in range(r_max+1)]
dp[0][0] = 1

for i in range(r_max+1):
    for j in range(b_max+1):
        tot = i+j
        if(rb_use[0][tot] >= i)&(rb_use[1][tot] >= j):
            if(i==0)&(j==0):
                continue
            elif(i==0):
                dp[i][j] = dp[i][j-1]
            elif(j==0):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = (dp[i][j-1] + dp[i-1][j])%mod

print(dp[-1][-1])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] % md * ifac[com_n - com_r] % md



md = 998244353
n_max = 4005
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def solve():
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    r = b = 0
    for i, c in enumerate(s):
        if c == "0": r += 2
        elif c == "2": b += 2
        else: r, b = r + 1, b + 1
        for j in range(n):
            pre = dp[i][j]
            if pre == 0: continue
            if j + 1 <= r: dp[i + 1][j + 1] += pre
            if i + 1 - j <= b: dp[i + 1][j] += pre
    
    ans = 0
    for j in range(n + 1):
        ans += dp[n][j] * nCr(n, r - j)
        ans %= md
    print(ans)

s=SI()
n=len(s)
solve()

Solution (Python):
mod = 998244353
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 10**5 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


import sys
input = sys.stdin.readline

S = list(input().rstrip())

L = len(S)
dp = [[0]*(L+1) for _ in range(L+1)]
dp[0][0] = 1
rmax = [0, 0]
rmin = [0, 0]
rsum = 0
for i, s in enumerate(S):
    p = int(s)
    rsum += p
    if p == 0:
        rmin[1] += 2
    elif p == 1:
        rmax[1] += 1
        rmin[1] += 1
    else:
        rmax[1] += 2
    if rmax[1] > 0:
        rmax[0] += 1
        rmax[1] -= 1
    if rmin[1] > 0:
        rmin[0] += 1
        rmin[1] -= 1
    for j in range(i+1):
        if rmax[0] >= j+1:
            dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % mod
        if rmin[0] >= (i+1) - j:
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % mod


ans = 0
for j in range(L+1):
    ans = (ans + dp[L][j] * cmb(L, rsum-j)) % mod
print(ans)

Solution (Python):
S=input()
N=len(S)
mod=998244353
red=[0]*N
blue=[0]*N
for i in range(N):
    if S[i]=="0":
        red[i]+=2
    elif S[i]=="1":
        red[i]+=1
        blue[i]+=1
    else:
        blue[i]+=2
    if i!=0:
        red[i]+=red[i-1]
        blue[i]+=blue[i-1]
R=red[-1]
B=blue[-1]

dp=[[0 for i in range(2*N+1)] for i in range(2*N+1)]

dp[2*N][R]=1

for i in range(2*N-1,-1,-1):
    for j in range(2*N+1):
        if i>=N:
            r=R-j
            b=B-(i-j)
            if r and 2*N>=j+1:
                dp[i][j]+=dp[i+1][j+1]
                dp[i][j]%=mod
            if b:
                dp[i][j]+=dp[i+1][j]
                dp[i][j]%=mod
        else:
            r=red[i]-j
            b=blue[i]-(i-j)
            if r and 2*N>=j+1:
                dp[i][j]+=dp[i+1][j+1]
                dp[i][j]%=mod
            if b:
                dp[i][j]+=dp[i+1][j]
                dp[i][j]%=mod


print(dp[0][0])

Solution (Python):
import sys
input = sys.stdin.readline
S = list(map(int, list(input())[: -1]))
mod = 998244353

N = len(S)
S += [0] * N
dp = [[0] * (N * 2 + 1) for _ in range(2 * N + 1)]
dp[0][0] = 1
for i in range(2 * N):
  x = S[i]
  for j in range(N * 2 + 1):
    if dp[i][j]:
      if (j + x) in range(N * 2 + 1):
        if (j + x) <= i + 1:
          dp[i + 1][j + x] += dp[i][j]
          dp[i + 1][j + x] %= mod
      if (j + x - 1) in range(N * 2 + 1):
        dp[i + 1][j + x - 1] += dp[i][j]
        dp[i + 1][j + x - 1] %= mod
print(dp[-1][0])

Solution (Python):
import sys
input = sys.stdin.readline

S = input()[:-1]
N = len(S)
dp = [[0]*(2*N+1) for _ in range(2*N+1)]
dp[0][0] = 1
MOD = 998244353
r, b = 0, 0

for i in range(2*N):
    if i<N:
        if S[i]=='0':
            r += 2
        elif S[i]=='1':
            r += 1
            b += 1
        else:
            b += 2
        
    for j in range(2*N+1):
        rc = r-j
        bc = b-(i-j)
        
        if rc>0:
            dp[i+1][j+1] += dp[i][j]
            dp[i+1][j+1] %= MOD
        
        if bc>0:
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
    
print(sum(dp[2*N]))

Solution (Python):

def main():
    s = list(map(int, list(input())))
    n = len(s)
    dp = [1]
    mod = 998244353
    for i, c in enumerate(s):
        dp2 = [0]*(i+2)
        for r in range(i+1):
            if r+c > 0:
                dp2[r+c-1] = (dp2[r+c-1]+dp[r]) % mod
            if i+2-r-c > 0:
                dp2[r+c] += (dp2[r+c]+dp[r]) % mod
        dp = dp2
    for i in range(n):
        dp2 = [0]*(n-i)
        for r in range(n-i+1):
            if r > 0:
                dp2[r-1] = (dp2[r-1]+dp[r]) % mod
            if n-i-r > 0:
                dp2[r] = (dp2[r]+dp[r]) % mod
        dp = dp2
    print(dp[0] % mod)


main()

Solution (Python):
mod = 998244353
s = list(map(int, list(input())))
n = len(s)
dp = [[0]*(sum(s)+1) for _ in range(2*n+1)]
dp[0][0] = 1
curr = curb = 0
for i in range(2*n):
  if i < n:
    curb += s[i]
    curr += 2 - s[i]
  for j in range(min(i, curb)+1):
    if dp[i][j]:
      dp[i][j] %= mod
      if i - j < curr:
        dp[i+1][j] += dp[i][j]
      if j < curb:
        dp[i+1][j+1] += dp[i][j]
print(dp[2*n][curb] % mod)

Solution (Python):
s = input()
n = len(s)
red = [0]
blue = [0]
mod = 998244353
red = [-1]*(2*n)
blue = [-1]*(2*n)
cntr = 0
cntb = 0
for i in range(n):
  cntr = max(cntr,i)
  cntb = max(cntb,i)
  if s[i] == "0":
    red[cntr] = 1
    red[cntr+1] = 1
    cntr += 2
  if s[i] == "1":
    red[cntr] = 1
    cntr += 1
    blue[cntb] = 1
    cntb += 1
  if s[i] == "2":
    blue[cntb] = 1
    blue[cntb+1] = 1
    cntb += 2
for i in range(1,2*n):
  red[i] += red[i-1]
  blue[i] += blue[i-1]
dp = [[0]*(4*n+5) for i in range(2*n+1)]
dp[0][0] = 1
for i in range(1,2*n+1):
  for j in range(-blue[i-1],red[i-1]+1,1):
    dp[i][j] = (dp[i-1][j+1]+dp[i-1][j-1])%mod

print(dp[-1][red[-1]])

Solution (Python):
"""

i回目では前からi人目の持っていた任意のボールを置ける
赤を何回採用したかでDP


"""

S = input()
N = len(S)
mod = 998244353

lis = [0] * (2*N+1)
lis[0] = 1
R = 0
B = 0

c = 0
for n in S:

    if n == "0":
        R += 2
    elif n == "1":
        R += 1
        B += 1
    else:
        B += 2

    nlis = [0] * (2*N+1)
    
    for i in range(2*N):

        if i < R:
            nlis[i+1] += lis[i]
            nlis[i+1] %= mod

        if c-i < B:
            nlis[i] += lis[i]
            nlis[i] %= mod

    lis = nlis
    c += 1


for loop in range(N):
    
    nlis = [0] * (2*N+1)
    
    for i in range(2*N):

        if i < R:
            nlis[i+1] += lis[i]
            nlis[i+1] %= mod

        if c-i < B:
            nlis[i] += lis[i]
            nlis[i] %= mod

    lis = nlis
    c += 1

print (sum(lis) % mod)

Solution (Python):
import sys
readline = sys.stdin.readline

S = list(map(int, readline().strip()))
N = len(S)
MOD = 998244353
dp = [[0]*(2*N+1) for _ in range(2*N+1)]
dp[0][0] = 1

B = [0]*(N+1)
for i in range(N):
    B[i+1] = B[i] + S[i]
B.extend([B[-1] for _ in range(N)])
R = [0] + [2*i - B[i] for i in range(1, N+1)]
R.extend([R[-1] for _ in range(N)])

for i in range(2*N):
    for j in range(2*N+1):
        if not dp[i][j]:
            continue
        
        b = B[i+1] - j
        r = R[i+1] - (i - j)
        if b > 0:
            dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j])%MOD
        if r > 0:
            dp[i+1][j] = (dp[i+1][j] + dp[i][j])%MOD
print(dp[2*N][sum(S)])

Solution (Python):
S = input()
N = len(S)
mod = 998244353

blue = [0] * N
red = [0] * N
for i in range(N):
    blue[i] = blue[i-1] + int(S[i])
    red[i] = red[i-1] + 2 - int(S[i])

dp = [[0 for _ in range(blue[-1] + 1)] for _ in range(2*N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(blue[-1]+1):
        if j + 1 <= blue[i]:
            dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % mod
        if i+1-j <= red[i]:
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % mod
for i in range(N, 2*N):
    for j in range(blue[-1]+1):
        if j+1 <= blue[-1]:
            dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % mod
        dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod

print(dp[-1][-1])

Solution (Python):
import os
import sys

import numpy as np
from scipy.misc import comb

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18

MOD = 998244353


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = []
    r = 1
    for inv in mod_invs(max, mod):
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


S = list(map(int, list(sys.stdin.readline().rstrip())))
N = len(S)


dp = np.zeros((N + 1, N + 10), dtype=int)
dp[0][0] = 1

for i in range(N):
    if S[i] == 2:
        
        dp[i + 1][1:] += dp[i][:-1]
        
        dp[i + 1][2:i + 2] += dp[i][:i]
    if S[i] == 1:
        
        dp[i + 1] += dp[i]
        
        dp[i + 1][1:] += dp[i][:-1]
    if S[i] == 0:
        
        dp[i + 1][:-1] += dp[i][1:]
        
        dp[i + 1] += dp[i]
    dp[i + 1] %= MOD

comb = Combination(max=N, mod=MOD)
ans = 0
for c, cnt in enumerate(dp[-1]):
    
    ans += comb.ncr(N, c) * cnt
    ans %= MOD
    

print(ans)

Solution (Python):










from itertools import accumulate
import numpy as np

def main():
    mod = 998244353
    B = list(map(int, input()))
    N = len(B)
    A = [2-b for b in B] + [0]*N
    B += [0] * N
    a = b = 0
    for i in range(2*N):
        b += B[i]
        if b > 0:
            b -= 1
            B[i] = 1
        a += A[i]
        if a > 0:
            a -= 1
            A[i] = 1

    A = list(accumulate(A))
    B = list(accumulate(B))

    dp = np.zeros((2*N+1, 2*N+1), dtype=np.int64)
    dp[0, 0] = 1
    for i, (a, b) in enumerate(zip(A, B), 1):
        dp[i, :] = dp[i-1, :]
        dp[i, 1:] = (dp[i, 1:] + dp[i-1, :-1]) % mod
        dp[i, :i-b] = 0
        dp[i, a+1:] = 0

    print(dp[2*N].sum() % mod)

main()

Solution (Python):










from itertools import accumulate

def main():
    mod = 998244353
    B = list(map(int, input()))
    N = len(B)
    A = [2-b for b in B] + [0]*N
    B += [0] * N
    a = b = 0
    for i in range(2*N):
        b += B[i]
        if b > 0:
            b -= 1
            B[i] = 1
        a += A[i]
        if a > 0:
            a -= 1
            A[i] = 1

    A = list(accumulate(A))
    B = list(accumulate(B))

    dp = [[0]*(2*N+2) for _ in range(2*N+1)]
    dp[0][0] = 1
    for i, (a, b) in enumerate(zip(A, B), 1):
        for j in range(2*N+1):
            if i - b <= j <= a:
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod

    print(sum(dp[2*N]) % mod)

main()

Solution (Python):
mod = 998244353
import sys
sys.setrecursionlimit(10**9)
S = input()
N = len(S)
Sum = [0]*(N+1)
for i in range(1, N+1):
    Sum[i] = Sum[i-1]+int(S[i-1])
dp = [[0]*(N*2+1) for _ in range(N*2+1)]
for i in range(N*2+1)[::-1]:
    for j in range(N*2+1)[::-1]:
        if i+j == N*2:
            dp[i][j] = 1
            continue
        n = min(i+j+1, N)
        s = Sum[n]
        if i<s:
            dp[i][j]+=dp[i+1][j]
        if 2*n-s>j:
            dp[i][j]+=dp[i][j+1]
        dp[i][j]%=mod
print(dp[0][0])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

S = input().rstrip()
N = len(S)


blue = 0
red = 0

dp = np.array([1], dtype=np.int64)
for i in range(2*N):
    if i < N:
        blue += int(S[i])
        red = 2 * (i+1) - blue
    prev = dp
    dp = np.zeros(blue+1, dtype=np.int64)
    
    L = min(len(prev), blue)
    dp[1:L+1] += prev[:L]
    
    dp[:len(prev)] += prev
    
    min_blue = (i+1) - red
    if min_blue >= 1:
        dp[:min_blue] = 0
    dp %= MOD

answer = dp[-1]
print(answer)

Solution (Python):
from itertools import accumulate
S=input()
l=len(S)
mod=998244353
R_cnt,B_cnt=[],[]
for i in S:
    R_cnt.append(2-int(i))
    B_cnt.append(int(i))
R_acc=[0]+list(accumulate(R_cnt))
R_acc+=[R_acc[-1]]*l
B_acc=[0]+list(accumulate(B_cnt))
B_acc+=[B_acc[-1]]*l
DP=[[0]*(2*l+1) for _ in range(2*l+1)]
DP[0][0]=1
for i in range(2*l):
    for r in range(i+1):
        if R_acc[i+1]>=r+1:
            DP[i+1][r+1]+=DP[i][r]
            DP[i+1][r+1]%=mod
        if B_acc[i+1]>=i+1-r:
            DP[i+1][r]+=DP[i][r]
            DP[i+1][r]%=mod
print(DP[-1][R_acc[-1]])

Solution (Python):
from itertools import accumulate
S=input()
l=len(S)
mod=998244353
R_cnt,B_cnt=[],[]
for i in S:
    R_cnt.append(2-int(i))
    B_cnt.append(int(i))
R_acc=[0]+list(accumulate(R_cnt))
R_acc+=[R_acc[-1]]*l
B_acc=[0]+list(accumulate(B_cnt))
B_acc+=[B_acc[-1]]*l
DP=[[0]*(2*l+1) for _ in range(2*l+1)]
DP[0][0]=1
for i in range(2*l):
    for r in range(i+1):
        if R_acc[i+1]>=r+1:
            DP[i+1][r+1]+=DP[i][r]
            DP[i+1][r+1]%=mod
        if B_acc[i+1]>=i+1-r:
            DP[i+1][r]+=DP[i][r]
            DP[i+1][r]%=mod
print(max(DP[-1]))

Solution (Python):
s = input()
MOD = 998244353
cnt_r = []
cnt_b = []
for i in s:
    cnt_r.append(2-int(i))
    cnt_b.append(int(i))
cursum_cnt_r = [0]*(len(s)+1)
cursum_cnt_b = [0]*(len(s)+1)
for i in range(len(s)):
    cursum_cnt_r[i+1] = cursum_cnt_r[i] + cnt_r[i]
    cursum_cnt_b[i+1] = cursum_cnt_b[i] + cnt_b[i]
cursum_cnt_r = cursum_cnt_r + [cursum_cnt_r[-1]]*len(s)
cursum_cnt_b = cursum_cnt_b + [cursum_cnt_b[-1]]*len(s)


dp = [[0]*(2*len(s)+1) for i in range(2*len(s)+1)]
dp[0][0] = 1
for ni in range(1,2*len(s)+1):
    for ri in range(0,ni+1):
        if ri == 0:
            if 0 <= ni <= cursum_cnt_b[ni]:
                
                dp[ni][ri] = dp[ni-1][ri]
        elif ri == ni:
            if 0 <= ri <= cursum_cnt_r[ni]:
                
                dp[ni][ri] = dp[ni-1][ri-1]
        else:
            if 0 <= ri <= cursum_cnt_r[ni] and 0 <= ni-ri <= cursum_cnt_b[ni]:
                dp[ni][ri] += dp[ni-1][ri]
                dp[ni][ri] += dp[ni-1][ri-1]
        dp[ni][ri] %= MOD 

print(max(dp[2*len(s)]))

Solution (Python):

import sys

MOD = 998244353  

def comb(n, k):
    if k > n:
        return 0
    k = min(k, n - k)
    ret = 1
    for i in range(k):
        ret *= n - i
        ret //= i + 1
    return ret

def solve(S: str):
    n = len(S)
    b_total = 0
    b_counts = []
    for c in S:
        b_total += ord(c) - ord('0')
        b_counts.append(b_total)
    dp = [[0] * (b_total + 1) for _ in range(2 * n + 1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(min(i + 1, b_total + 1)):
            if b_counts[i] >= j + 1:
                dp[i + 1][j + 1] += dp[i][j]
            if (i + 1) * 2 - b_counts[i] >= (i + 1) - j:
                dp[i + 1][j] += dp[i][j]
    
    
    comb = [0] * (n + 1)
    comb[0] = 1
    for i in range(n):
        comb[i + 1] = comb[i] * (n - i) // (i + 1)
    ret = 0
    for b, val in enumerate(dp[n]):
        
        if b_total - b >= 0 and b_total - b <= n:
            ret += val * comb[b_total - b]
    print(ret % MOD)
    return

    
    
    
    
    
    
    
    
    
    
    
    


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))
    solve(S)

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007


"""
n,k = LI()
if 2*(k-1) < n:
    print("YES")
else:
    print("NO")
"""


"""
c = LIR(3)
v = [[] for i in range(4)]
for i in range(3):
    c[i][0] -= 1
    c[i][1] -= 1
    v[c[i][0]].append(c[i][1])
    v[c[i][1]].append(c[i][0])

for i in range(4):
    li = [True for i in range(4)]
    li[i] = False
    q = [i]
    c = 0
    while q:
        x = q.pop(-1)
        k = 0
        for j in v[x]:
            if li[j]:
                li[j] = False
                q.append(j)
                if k == 0:
                    c += 1
                    k += 1
    if c == 3:
        print("YES")
        quit()
print("NO")
"""


"""
k,a,b = LI()
if k <= a:
    print(k+1)
else:
    if b-a < 3:
        print(k+1)
    else:
        ans = a+((k-a+1)//2)*(b-a)+(k-a+1)%2
        print(ans)
"""




"""
n,m = LI()
a = LIR(n)
a.sort()
a = a[::-1]
for i in range(n):
    for j in range(i+1,n):
        s = 0
        while a[i][s] == 0 and s < m-1:s+=1
        if s < m and a[i][s] != 0:
            if a[j][s] > 0:
                for k in range(s,m):
                    a[j][k] -= 1*a[i][k]
                    a[j][k] = abs(a[j][k])
r = 0
for i in range(n):
    if sum(a[i]) > 0:r += 1
print((pow(2,n+m-1)-pow(2,n-r+m-1))%998244353)
"""


mod = 998244353
s = list(sys.stdin.readline().strip())
n = len(s)
dp = [[0 for i in range(2*n+1)] for j in range(2*n+1)]
r = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n):
    b[i] = int(s[i])
    r[i] = 2-b[i]
for i in range(n-1):
    r[i+1] += r[i]
    b[i+1] += b[i]
r.insert(0,0)
b.insert(0,0)
if r[1] > 0:
    dp[1][1] = 1
for i in range(1,2*n+1):
    if b[min(i,n)] < i:break
    if b[min(i,n)] >= i:dp[i][0] = 1
for i in range(2,n+1):
    for j in range(1,2*n+1):
        if r[i] >= j:
            dp[i][j] += dp[i-1][j-1]
            dp[i][j] %= mod
        if b[i] >= i-j:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod
for i in range(n+1,2*n+1):
    for j in range(1,2*n+1):
        if r[n] >= j:
            dp[i][j] += dp[i-1][j-1]
            dp[i][j] %= mod
        if b[n] >= i-j:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod

print(dp[2*n][r[-1]])

Solution (Python):
from collections import defaultdict
def inpl(): return list(map(int, input().split()))
MOD = 998244353

S = input()
N = len(S)
B = [0]*(2*N+1)
R = [0]*(2*N+1)

for i in range(N):
    b = int(S[i])
    B[i] = b
    R[i] = 2 - b

DP = defaultdict(int)
DP[(B[0], R[0])] = 1

for i in range(1, 2*N+1):
    DP2 = defaultdict(int)
    b1, r1 = B[i], R[i]
    for (b0, r0), v in DP.items():
        b2, r2 = b0+b1, r0+r1
        if b0:
            DP2[(b2-1, r2)] = (DP2[(b2-1, r2)] + v)%MOD
        if r0:
            DP2[(b2, r2-1)] = (DP2[(b2, r2-1)] + v)%MOD
    DP = DP2

print(sum(DP.values()))

Solution (Python):
from collections import defaultdict
def inpl(): return list(map(int, input().split()))
MOD = 998244353

S = input()
N = len(S)
B = [0]*N
R = [0]*N

for i in range(N):
    b = int(S[i])
    B[i] = b
    R[i] = 2 - b

DP = defaultdict(int)
DP[(B[0], R[0])] = 1

for i in range(1, N):
    DP2 = defaultdict(int)
    b1, r1 = B[i], R[i]
    for (b0, r0), v in DP.items():
        b2, r2 = b0+b1, r0+r1
        if b0:
            DP2[(b2-1, r2)] = (DP2[(b2-1, r2)] + v)%MOD
        if r0:
            DP2[(b2, r2-1)] = (DP2[(b2, r2-1)] + v)%MOD
    DP = DP2

for _ in range(N+1):
    DP2 = defaultdict(int)
    for (b, r), v in DP.items():
        if b:
            DP2[(b-1, r)] = (DP2[(b-1, r)] + v)%MOD
        if r:
            DP2[(b, r-1)] = (DP2[(b, r-1)] + v)%MOD
    DP = DP2

print(sum(DP.values()))

Solution (Python):
S=input()
N=len(S)
mod=998244353
L=[0]*(2*N)
L[0]=int(S[0])
for i in range(1,N):
    L[i]=L[i-1]+int(S[i])
for i in range(N,2*N):
    L[i]=L[i-1]
dp=[[0]*(2*N+1) for i in range(2*N+1)]
dp[0][0]=1
for n in range(1,2*N+1):
    for k in range(min(n,L[n-1])+1):
        if n-k>2*n-L[n-1]:
            continue
        dp[n][k]+=dp[n-1][k]
        dp[n][k]%=mod
        if k>=1:
            dp[n][k]+=dp[n-1][k-1]
            dp[n][k] %= mod
ans=dp[2*N][L[-1]]
print(ans)

Solution (Python):
S = input()
N = len(S)

redarray = [0] * (N+1)
bluarray = [0] * (N+1)

for e,c in enumerate(S):

    if c == "2":
        bluarray[e+1] += 2
    elif c == "1":
        redarray[e+1] += 1
        bluarray[e+1] += 1
    elif c == "0":
        redarray[e+1] += 2

for i in range(1,N+1):
    redarray[i] += redarray[i-1]
    bluarray[i] += bluarray[i-1]

dp = [ [0] * (2*N+1) for _ in range(2*N+1)]
dp[0][0] = 1
MOD = 998244353

for p in range(1, 2*N+1):
    for r in range(0, p):
        idx = p if p <= N else N
        if r < redarray[idx]:
            dp[p][r+1] += dp[p-1][r] % MOD
        if p-1-r < bluarray[idx]:
            dp[p][r] += dp[p-1][r] % MOD

print(dp[2*N][redarray[N]]%MOD)

Solution (Python):
S = input()
N = len(S)

from collections import defaultdict

reddic = defaultdict(int)
bludic = defaultdict(int)

redarray = [0] * (N+1)
bluarray = [0] * (N+1)

for e,c in enumerate(S):

    if c == "2":
        bludic[e+1] += 2
        bluarray[e+1] += 2
    elif c == "1":
        reddic[e+1] += 1
        bludic[e+1] += 1

        redarray[e+1] += 1
        bluarray[e+1] += 1
    elif c == "0":
        reddic[e+1] += 2
        redarray[e+1] += 2

for i in range(1,N+1):
    redarray[i] += redarray[i-1]
    bluarray[i] += bluarray[i-1]




dp = [ [0] * (2*N+1) for _ in range(2*N+1)]
dp[0][0] = 1
MOD = 998244353

for p in range(1, 2*N+1):
    for r in range(0, p):
        idx = p if p <= N else N
        if r < redarray[idx]:
            dp[p][r+1] += dp[p-1][r] % MOD
        if p-1-r < bluarray[idx]:
            dp[p][r] += dp[p-1][r] % MOD
    

print(dp[2*N][redarray[N]]%MOD)

Solution (Python):
import numpy as np


def prepare(n):
    f = 1
    for i in range(2, n + 1):
        f = f * i % MOD
    inv = [1] * (n + 1)
    inv[n] = pow(f, MOD - 2, MOD)
    for i in range(n, 0, -1):
        inv[i - 1] = inv[i] * i % MOD
    return f, inv


MOD = 998244353
s = input()
n = len(s)
dp = np.zeros(n + 1, dtype=np.int64)
dp[0] = 1
b_all = 0
i, j = 0, 1
for k in range(n):
    b_all += int(s[k])
    ball = 2 * (k + 1)
    dp += np.roll(dp, 1)
    dp %= MOD
    if j <= ball - b_all:
        j += 1
    else:
        dp[j] = 0
    if k - i < b_all:
        pass
    else:
        dp[i] = 0
        i += 1
r_all = 2 * n - b_all
f, inv = prepare(n)
ans = 0
for k in range(i, j):
    r = r_all - k
    b = n - r
    ans += dp[k] * f % MOD * inv[r] % MOD * inv[b]
    ans %= MOD
print(ans)

Solution (Python):
M=998244353
S=input()
N=len(S)
d=[[0]*4001 for _ in range(4001)]
d[0][0]=1
x=0
for i in range(2*N):
	if i<N:
		x+=int(S[i])
		y=2*i+2-x
	for j in range(i+1):
		for k in range(2):d[j+1-k][i-j+k]+=i-y<=j-k<x and d[j][i-j]%M
print(d[x][y]%M)

Solution (Python):
M=998244353
S=input()
N=len(S)
d=[[0]*4001 for _ in range(4001)]
d[0][0]=1
x=0
for i in range(2*N):
	if i<N:
		x+=int(S[i])
		y=2*i+2-x
	for j in range(i+1):
		for k in range(2):
			if i-y<=j-k<x:d[j+1-k][i-j+k]+=d[j][i-j]%M
print(d[x][y]%M)

Solution (Python):
S=input()
N=len(S)
d=[[0]*4001 for _ in range(4001)]
d[0][0]=1
x=0
y=0
for i in range(2*N):
	if i<N:
		x+=int(S[i])
		y=2*i+2-x
	for j in range(i+1):
		for k in range(2):
			if j+1-k<=x and i-j+k<=y:
				d[j+1-k][i-j+k]+=d[j][i-j]
				d[j+1-k][i-j+k]%=998244353
print(d[x][y])

Solution (Python):
s = input()
n = len(s)
mod = 998244353

R = [0] * n
B = [0] * n
for i in range(n):
    if s[i] == '0':
        R[i] = 2
    elif s[i] == '1':
        R[i] = 1
        B[i] = 1
    else:
        B[i] = 2

for i in range(n-1):
    R[i+1] += R[i]
    B[i+1] += B[i]


dp = [[0] * (2*n+10) for _ in range(2*n+10)]

if R[0] > 0:
    dp[0][1] = 1
if B[0] > 0:
    dp[0][0] = 1

for i in range(n-1):
    for r in range(2*n+1):
        if R[i+1] >= r+1:
            dp[i+1][r+1] += dp[i][r]
            dp[i+1][r+1] %= mod
        if i+2-r < 0:
            break
        if B[i+1] >= i+2-r:
            dp[i+1][r] += dp[i][r]
            dp[i+1][r] %= mod

for i in range(n-1, 2*n-1):
    for r in range(2*n+1):
        if R[n-1] >= r+1:
            dp[i + 1][r + 1] += dp[i][r]
            dp[i + 1][r + 1] %= mod
        if i+2-r < 0:
            break
        if B[n-1] >= i+2-r:
            dp[i+1][r] += dp[i][r]
            dp[i+1][r] %= mod

ans = 0
for r in range(2*n+1):
    ans += dp[2*n-1][r]
    ans %= mod

print(ans)