Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):

"""
無理な場合を考えてみよう
→全体の辺の本数が奇数なら絶対無理

それ以外は？
説1:辺が偶数なら絶対作れる説

辺を選択し、そのどちらか片方にのみ xor1する
→すべての辺の数字を0にできるか？？(初期値は0)
なんかできそう

辺の向きを変えることで1を伝播させることが出来る
→同じ点にぶつけられる！！
ので、偶数本なら絶対できる


どうやって構成する？
適当に置く→1の点を適当に2つ選び、パス上にある辺を全部反転させる
確かにできるけど…遅くね？

もっと簡単にできないか？
適当に木を取る→深い方から整合性を合わせていけば終わり(最終的には根に収束するので)
各点に関して動かすのは高々1辺だけだから、木を取った辺のみ考えて反転させる
(それ以外は適当に置いておく)

dfsで終わり→解けた！！！
"""
import sys
N,M = map(int,input().split())

lisD = [ [] for i in range(N) ]
lisN = [ [] for i in range(N) ]
xorlis = [0] * N
AB = []

for i in range(M):

    a,b = map(int,input().split())
    AB.append([a,b])
    a -= 1
    b -= 1

    lisD[a].append([b,i])
    lisN[a].append([b,i])
    lisN[b].append([a,i])
    xorlis[b] ^= 1

visited = [False] * N
def dfs(now):

    visited[now] = True

    for nex,eind in lisN[now]:
        if visited[nex]:
            continue
        cat = dfs(nex)
        if cat != 0:
            xorlis[nex] ^= 1
            xorlis[now] ^= 1
            t = AB[eind][1]
            AB[eind][1] = AB[eind][0]
            AB[eind][0] = t

    return xorlis[now]

dfs(0)
if xorlis[0] == 1:
    print (-1)
    sys.exit()

else:
    for i,j in AB:
        print (i,j)


Fixed submission:

"""
無理な場合を考えてみよう
→全体の辺の本数が奇数なら絶対無理

それ以外は？
説1:辺が偶数なら絶対作れる説

辺を選択し、そのどちらか片方にのみ xor1する
→すべての辺の数字を0にできるか？？(初期値は0)
なんかできそう

辺の向きを変えることで1を伝播させることが出来る
→同じ点にぶつけられる！！
ので、偶数本なら絶対できる


どうやって構成する？
適当に置く→1の点を適当に2つ選び、パス上にある辺を全部反転させる
確かにできるけど…遅くね？

もっと簡単にできないか？
適当に木を取る→深い方から整合性を合わせていけば終わり(最終的には根に収束するので)
各点に関して動かすのは高々1辺だけだから、木を取った辺のみ考えて反転させる
(それ以外は適当に置いておく)

dfsで終わり→解けた！！！
"""
import sys
sys.setrecursionlimit(200000)
N,M = map(int,input().split())

lisN = [ [] for i in range(N) ]
xorlis = [0] * N
AB = []

if M % 2 == 1:
    print (-1)
    sys.exit()

for i in range(M):

    a,b = map(int,input().split())
    AB.append([a,b])
    a -= 1
    b -= 1

    lisN[a].append([b,i])
    lisN[b].append([a,i])
    xorlis[b] ^= 1

visited = [False] * N
def dfs(now):

    visited[now] = True

    for nex,eind in lisN[now]:
        if visited[nex]:
            continue
        cat = dfs(nex)
        if cat != 0:
            xorlis[nex] ^= 1
            xorlis[now] ^= 1
            t = AB[eind][1]
            AB[eind][1] = AB[eind][0]
            AB[eind][0] = t

    return xorlis[now]

dfs(0)
#print (xorlis)
if 1 in xorlis:
    print (-1)
    sys.exit()

else:
    for i,j in AB:
        print (j,i)
Buggy python submission (verdict: Runtime Error):
import math
import fractions
import numpy

np.set_printoptions(suppress=True)


A,B,C,D = map(int,input().split())

G = C * D / fractions.gcd(C,D)

ans = int( B // C - (A-1) // C ) + int(B // D - (A-1) // D) - int(B // G - (A-1) // G)

print (B - A + 1 - ans)


Fixed submission:
from decimal import Decimal

	
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)


A,B,C,D = map(int,input().split())
A = Decimal(str(A))
B = Decimal(str(B))
C = Decimal(str(C))
D = Decimal(str(D))

G = C * D / gcd(C,D)

#print('{:.100g}'.format(G))

ans = ( B // C - (A-1) // C ) + (B // D - (A-1) // D) - (B // G - (A-1) // G)

print ('{:.100g}'.format(B - A + 1 - ans))
Buggy python submission (verdict: Time Limit Exceeded):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_e
Mの時、 a1<=a2<=a3…aN
を満たす通り数 X[M] が分かれば解ける(全ての順N!は等しいため)

当然、次のMにはa1から順に更新していくことになる(M+?にね)
Dの時
X[M] = (X[M-1] + X[M-2] +　… + X[M-D]) * N
が成立かな
X[0] = 1

N=2
X[0]=1
X[1]=2
X[2]=6

N=3
X[0]=1
X[1]=9

X[M]の更新式
→これが間違ってそう
X[M] = (X[M-1] + X[M-2] +　… + X[M-D]) * (1!+2!+3!+…N!)
→エスパーだけどなんか正しそう

X[H-1]を求めてN!を掛ければそれが答え
→サンプル合った！！
"""
import math
N,H,D = map(int,input().split())
mod = 10**9+7

mul = 0
fac = 1
for i in range(1,N+1):
    fac *= i
    fac %= mod
    mul += fac
    mul %= mod

X = [1]
nsum = 1
for i in range(H-1):

    #print (i,nsum,mul)
    X.append(nsum*mul%mod)

    nsum += X[-1]
    if i >= D-1:
        nsum -= X[i-D+1]
        

#print (X)
print (nsum * math.factorial(N) % mod)


Fixed submission:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_e
Mの時、 a1<=a2<=a3…aN
を満たす通り数 X[M] が分かれば解ける(全ての順N!は等しいため)

当然、次のMにはa1から順に更新していくことになる(M+?にね)
Dの時
X[M] = (X[M-1] + X[M-2] +　… + X[M-D]) * N
が成立かな
X[0] = 1

N=2
X[0]=1
X[1]=2
X[2]=6

N=3
X[0]=1
X[1]=9

X[M]の更新式
→これが間違ってそう
X[M] = (X[M-1] + X[M-2] +　… + X[M-D]) * (1!+2!+3!+…N!)
→エスパーだけどなんか正しそう

X[H-1]を求めてN!を掛ければそれが答え
→サンプル合った！！
"""
import math
N,H,D = map(int,input().split())
mod = 10**9+7

mul = 0
fac = 1
for i in range(1,N+1):
    fac *= i
    fac %= mod
    mul += fac
    mul %= mod

X = [1]
nsum = 1
for i in range(H-1):

    #print (i,nsum,mul)
    X.append(nsum*mul%mod)

    nsum += X[-1]
    nsum %= mod
    if i >= D-1:
        nsum -= X[i-D+1]
        

#print (X)
print (nsum * fac % mod)
Buggy python submission (verdict: Time Limit Exceeded):

H,W = input().split()
H = int(H)
W = int(W)
S = []

for i in range(H):

    sp = input()
    S.append(sp)

maxi = 0
now = 0

for i in range(H):

    for j in range(W):

        if ( S[i][j] != "#"):

            now = 1

            for k in range(j):
                k = j - 1 - k

                if (S[i][k] == "."):
                    now += 1

                else:
                    break

            for k in range(W - 1 - j):
                k = j + 1 + k

                if (S[i][k] == "."):
                    now += 1

                else:
                    break

            for k in range(i):
                k = i - 1 - k

                if (S[k][j] == "."):
                    now += 1

                else:
                    break

            for k in range(H - 1 - i):
                k = i + k + 1

                if (S[k][j] == "."):
                    now += 1

                else:
                    break


            if (maxi < now):
                maxi = now
            

print (maxi)


Fixed submission:

H,W = map(int,input().split())

S = []

for i in range(H):

    s = input()
    S.append(list(s))

yoko = []

for i in range(H):

    num = 0
    now = []

    for j in range(W):

        if S[i][j] == ".":
            num += 1

        else:
            now += ([num] * num)
            num = 0
            now.append(0)

    now += [num] * num
    yoko.append(now)

#print (yoko)

tate = []

for j in range(W):

    num = 0
    now = []

    for i in range(H):

        if S[i][j] == ".":
            num += 1

        else:
            now += ([num]*num)
            num = 0
            now.append(0)

    now += [num] * num
    tate.append(now)

ans = 0

for i in range(H):

    for j in range(W):

        ans = max(ans , yoko[i][j] + tate[j][i] - 1)

print (ans)
Buggy python submission (verdict: Time Limit Exceeded):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc129/tasks/abc129_f

Lが大きいので全探索は不可能
等差数列の桁数ごとに考える？

うしろから考えたほうがよさそうだ？
終項XはA+B*(L-1)　公差は-B の数列t0t1…と考えられる
桁数がkの所だけ考えると寄与の数列u0u1…は

========考察完了=========
桁別に分けて考える
まず桁数がkの奴がいくつあるか、最大の項は何か、それ以前に何桁あるか、が必要
→大きい方から見ていくか

あとは、桁ごとに寄与を計算し、式変形頑張れば解ける
"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

L,A,B,mod = map(int,input().split())

uzero = A+B*(L-1) #u0
ldig  = 0         #u0以前にいくつ桁が存在するか
dignum = len(str(uzero)) #uzeroの桁数

ans = 0
while True:

    if A > uzero: #Aより小さいなら飛ばす
        break
    
    #nは項数
    if 10**(dignum-1) <= A:
        n = (uzero-A)//B+1
    else:
        n = (uzero-A)//B - ((10**(dignum-1)-1)-A)//B


    S = (pow(10,n*dignum)-1) // (pow(10,dignum)-1)
    S %= mod

    Sd = (n-1)*pow(10,n*dignum)-(pow(10,dignum)*(pow(10,(n-1)*dignum)-1)//(pow(10,dignum)-1))
    Sd //= (pow(10,dignum)-1)
    Sd %= mod

    ans += uzero * S * pow(10,ldig,mod) - B * pow(10,ldig,mod)*Sd
    ans %= mod

    #print (uzero , ldig , n ,uzero * S , B * pow(10,ldig,mod)*Sd % mod)

    ldig += dignum * n
    uzero -= B*n
    dignum = len(str(uzero))

print (ans)
    
    


Fixed submission:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc129/tasks/abc129_f
=====解説をみた=====

なるほど行列式ね…
繰り返し同じ写像を繰り返す場合、行列式による繰り返し2乗法
を考えるべきなのかもしれんね…

"""

#行列A,Bの積(不可能だとエラー)
def matrix_mul(A,B):

    ans = [ [0] * len(B[0]) for i in range(len(A)) ]

    for ai in range(len(A)):

        for bj in range(len(B[0])):

            now = 0
            for same in range(len(A[0])):
                now += A[ai][same] * B[same][bj]
            ans[ai][bj] = now % mod

    return ans

#行列Aのx乗(当然正方行列じゃないとだめ)
def matrix_pow(A,x):

    B = [[A[i][j] for j in range(len(A[0]))] for i in range(len(A))]
    ans = [[0] * len(A[0]) for i in range(len(A))]
    for i in range(len(A)):
        ans[i][i] = 1

    while x > 0:
        if x % 2 == 1:
            ans = matrix_mul(ans,B)
        B = matrix_mul(B,B)

        x//=2
    return ans

import sys
L,A,C,mod = map(int,input().split())

now = [[0,A,1]]
LA = len(str(A))
LB = len(str(A+C*(L-1)))
B = A+C*(L-1)

if LA==LB:
    np = [[pow(10,LA,mod),0,0],[1,1,0],[0,C,1]]
    k = (B-A)//C+1
    now = matrix_mul(now , matrix_pow(np,k))
    print (now[0][0] % mod)
    sys.exit()

for i in range(LA,LB+1):

    np = [[pow(10,i,mod),0,0],[1,1,0],[0,C,1]]
    #print (now,np)

    if i == LA:
        k = (10**i-1-A)//C+1
        now = matrix_mul(now , matrix_pow(np,k))
    elif i == LB:
        k = (B-A)//C-(10**(i-1)-1-A)//C
        now = matrix_mul(now , matrix_pow(np,k))
    else:
        k = (10**i-1-A)//C - (10**(i-1)-1-A)//C
        now = matrix_mul(now , matrix_pow(np,k))

    #print (i,k,now)
print (now[0][0] % mod)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq

s = input()
s += " "

S = ""

for i in range(len(s)-1):
    if s[i] == "B" and s[i+1] == "C":
        S += "Z"

    elif i > 0 and s[i] == "C" and s[i-1] == "B":
        continue
    else:
        S += s[i]

#print (S)
la = deque([])
ans = 0
for i in range(len(S)):

    if S[i] == "A":
        la.append(i)

    elif S[i] == "Z" and len(la) > 0:
        lastA = la.popleft()
        ans += i - lastA
        la.append(i)

    else:
        la = deque()

print (ans)


Fixed submission:
from collections import deque
import heapq

s = input()
s += " "

S = ""

for i in range(len(s)-1):
    if s[i] == "B" and s[i+1] == "C":
        S += "Z"

    elif i > 0 and s[i] == "C" and s[i-1] == "B":
        continue
    else:
        S += s[i]

#print (S)
la = deque([])
ans = 0
for i in range(len(S)):

    if S[i] == "A":
        la.append(i)

    elif S[i] == "Z" and len(la) > 0:
        lastA = la.popleft()
        ans += i - lastA
        la.append(i)

    else:
        la = deque([])

print (ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq

s = input()
s += " "

S = ""

for i in range(len(s)-1):
    if s[i] == "B" and s[i+1] == "C":
        S += "Z"

    elif i > 0 and s[i] == "C" and s[i-1] == "B":
        continue
    else:
        S += s[i]

#print (S)
la = []
ans = 0
for i in range(len(S)):

    if S[i] == "A":
        heapq.heappush(la,i)

    elif S[i] == "Z" and len(la) > 0:
        lastA = heapq.heappop(la)
        ans += i - lastA
        heapq.heappush(la,i)

    else:
        la = []

print (ans)


Fixed submission:
from collections import deque
import heapq

s = input()
s += " "

S = ""

for i in range(len(s)-1):
    if s[i] == "B" and s[i+1] == "C":
        S += "Z"

    elif i > 0 and s[i] == "C" and s[i-1] == "B":
        continue
    else:
        S += s[i]

#print (S)
la = deque([])
ans = 0
for i in range(len(S)):

    if S[i] == "A":
        la.append(i)

    elif S[i] == "Z" and len(la) > 0:
        lastA = la.popleft()
        ans += i - lastA
        la.append(i)

    else:
        la = deque([])

print (ans)
Buggy python submission (verdict: Runtime Error):

S = input()

MAE = int(S[:2])
USIRO = int(S[2:])

MMYY_Flag = False
YYMM_Flag = False


if 1 <= MAE and 12 >= MAE:
    MMYY_Flag = True

if 1 <= USIRO and 12 >= USIRO:
    YYMM_Flag = True


if MMYY_Flag and YYMM_Flag:
    print ("AMBIGUOUS")

elif MMYY_Flag:
    print ("MMYY")
1700

elif YYMM_Flag:
    print ("YYMM")

else:
    print ("NA")


Fixed submission:

S = input()

MAE = int(S[:2])
USIRO = int(S[2:])

MMYY_Flag = False
YYMM_Flag = False


if 1 <= MAE and 12 >= MAE:
    MMYY_Flag = True

if 1 <= USIRO and 12 >= USIRO:
    YYMM_Flag = True


if MMYY_Flag and YYMM_Flag:
    print ("AMBIGUOUS")

elif MMYY_Flag:
    print ("MMYY")

elif YYMM_Flag:
    print ("YYMM")

else:
    print ("NA")
Buggy python submission (verdict: Time Limit Exceeded):

R,G,B,N = map(int,input().split())
ans = 0

for r in range(N // R + 1):

    for g in range( N // G + 1 ):

        if (N - r * R - g * G) >= 0 and (N - r * R - g * G) % B == 0:
            ans += 1

print (ans)


Fixed submission:

R,G,B,N = map(int,input().split())
ans = 0

for r in range(N // R + 1):

    for g in range( N // G + 1 ):

        if (N - r * R - g * G) >= 0 and (N - r * R - g * G) % B == 0:
            ans += 1

print (ans)
Buggy python submission (verdict: Runtime Error):

N = int(input())

ans = 0

now = 1

while now ** 2 <= N:

    if N % now == 0 and N // (N // now - 1) == N % (N // now - 1):

        ans += N // now - 1

    now += 1

print (ans)


Fixed submission:
N = int(input())

ans = 0

now = 1

while now ** 2 <= N:

    if N % now == 0 and (N // now - 1) > 0 and N // (N // now - 1) == N % (N // now - 1):

        ans += N // now - 1

    now += 1

print (ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque

N = int(input())

dic = {}

for  i in range(N-1):

    a,b = map(int,input().split())
    a-=1
    b-=1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

for xxx in range(1):

    lis = [float("inf")] * N
    lis[0] = 0
    maxind = 0
    q = deque([0])

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:

            if lis[nex] > lis[now] + 1:
                lis[nex] = lis[now] + 1
                q.append(nex)
                maxind = nex

    lis = [float("inf")] * N
    lis[maxind] = 1
    q = deque([maxind])
    L = 0

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:

            if lis[nex] > lis[now] + 1:
                lis[nex] = lis[now] + 1
                q.append(nex)
                L = lis[nex]

    #print (lis)
    #print (L)

    if L == 1 or L % 3 != 2:

        print ("First")

    else:

        print ("Second")


Fixed submission:
from collections import deque
import sys

N = int(input())

if N == 1:
    print ("First")
    sys.exit()


dic = {}

for  i in range(N-1):

    a,b = map(int,input().split())
    a-=1
    b-=1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

for xxx in range(1):

    lis = [float("inf")] * N
    lis[0] = 0
    maxind = 0
    q = deque([0])

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:

            if lis[nex] > lis[now] + 1:
                lis[nex] = lis[now] + 1
                q.append(nex)
                maxind = nex

    lis = [float("inf")] * N
    lis[maxind] = 1
    q = deque([maxind])
    L = 0

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:

            if lis[nex] > lis[now] + 1:
                lis[nex] = lis[now] + 1
                q.append(nex)
                L = lis[nex]

    #print (lis)
    #print (L)

    if L == 1 or L % 3 != 2:

        print ("First")

    else:

        print ("Second")
Buggy python submission (verdict: Time Limit Exceeded):
import fractions

N = int(input())

A = list(map(int,input().split()))
ans = 0
now_gcd = 0

for j in range(N):

    A_co = A.copy()
    del A_co[j]

    now_gcd = A_co[0]
    
    for i in range(N-2):

        now_gcd = fractions.gcd(now_gcd , A_co[i+1])

    if ans <= now_gcd:
        ans = now_gcd

print (ans)

Fixed submission:
import fractions

N = int(input())

A = list(map(int,input().split()))

L = [0] * N
R = [0] * N

now = A[0]
for i in range(N):

    if i >= 1:

        now = fractions.gcd(now,A[i-1])
        L[i] = now

A.reverse()

now = A[0]
for i in range(N):

    if i >= 1:

        now = fractions.gcd(now,A[i-1])
        R[i] = now

A.reverse()
R.reverse()

maxi = 0
for i in range(N):

    if L[i] == 0 or R[i] == 0:
        maxi = max(maxi,L[i],R[i])

    else:
        maxi = max(maxi, fractions.gcd(L[i],R[i]))

print (maxi)
Buggy python submission (verdict: Runtime Error):

N = int(input())

C = []

for i in range(N):

    c = int(input())

    if len(C) == 0 or C[-1] != c-1:
        C.append(c-1)

lis = []
last = [-1] * N

for i in range(len(C)):

    if i == 0:
        lis.append(1)
    
    elif last[C[i]] == -1 or last[C[i]] == i-1:
        lis.append(lis[-1])

    else:
        lis.append(lis[-1]+lis[last[C[i]]])

    last[C[i]] = i


print (lis[-1])

Fixed submission:

N = int(input())

C = []

for i in range(N):

    c = int(input())

    if len(C) == 0 or C[-1] != c-1:
        C.append(c-1)

lis = []
last = [-1] * (2 * (10**5))

for i in range(len(C)):

    if i == 0:
        lis.append(1)
    
    elif last[C[i]] == -1 or last[C[i]] == i-1:
        lis.append(lis[-1])

    else:
        lis.append(lis[-1]+lis[last[C[i]]])

    lis[-1] %= 10 ** 9 + 7
    last[C[i]] = i


print (lis[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

A,B,Q = map(int,input().split())

s = [-1 * float("inf")]
t = [-1 * float("inf")]

for i in range(A):

    S = int(input())
    s.append(S)

for i in range(B):

    T = int(input())
    t.append(T)

s.append(float("inf"))
t.append(float("inf"))

for i in range(Q):

    x = int(input())

    si = bisect.bisect_left(s,x)
    ti = bisect.bisect_left(t,x)

    now = min( max(s[si],t[ti]) - x  ,  x - min(s[si-1],t[ti-1]) )
    now = min( now , 2 * min( s[si] - x , x - t[ti-1] ) + max(s[si] - x , x - t[ti-1]))
    now = min( now , 2 * min( t[ti] - x , x - s[si-1] ) + max(t[ti] - x , x - s[si-1]))

    print (now)


Fixed submission:
import bisect

A,B,Q = map(int,input().split())

s = [-1 * float("inf")]
t = [-1 * float("inf")]

for i in range(A):

    S = int(input())
    s.append(S)

for i in range(B):

    T = int(input())
    t.append(T)

s.append(float("inf"))
t.append(float("inf"))

for i in range(Q):

    x = int(input())

    si = bisect.bisect_left(s,x)
    ti = bisect.bisect_left(t,x)

    now = min( max(s[si],t[ti]) - x  ,  x - min(s[si-1],t[ti-1]) )
    now = min( now , 2 * min( s[si] - x , x - t[ti-1] ) + max(s[si] - x , x - t[ti-1]))
    now = min( now , 2 * min( t[ti] - x , x - s[si-1] ) + max(t[ti] - x , x - s[si-1]))

    print (now)
Buggy python submission (verdict: Time Limit Exceeded):
"""

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)

Fixed submission:
"""

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)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N,M = map(int,input().split())

dic = {}
npflag = [True] * N
p = [None] * N
dep = [float("-inf")] * N

for i in range(N+M-1):

    A,B = map(int,input().split())
    A -= 1
    B -= 1

    if A not in dic:
        dic[A] = []

    dic[A].append(B)
    npflag[B] = False

for i in range(N):

    if npflag[i]:
        root = i
        break

p[i] = -1
q = deque([i])
dep[i] = 0

while len(q) > 0:

    now = q.popleft()

    if now in dic:
        for i in dic[now]:

            if p[i] == None:
                p[i] = now
                dep[i] = dep[now] + 1
                q.append(i)

            elif dep[i] < dep[now] + 1:
                p[i] = now
                dep[i] = dep[now] + 1
                q.append(i)

for i in range(N):

    print (p[i]+1)

Fixed submission:
from collections import deque

N,M = map(int,input().split())

dic = {}
npflag = [True] * N
pnum = [0] * N
p = [None] * N
dep = [float("-inf")] * N

for i in range(N+M-1):

    A,B = map(int,input().split())
    A -= 1
    B -= 1

    if A not in dic:
        dic[A] = []

    dic[A].append(B)
    npflag[B] = False
    pnum[B] += 1

for i in range(N):

    if npflag[i]:
        root = i
        break

p[i] = -1
q = deque([i])
dep[i] = 0

while len(q) > 0:

    now = q.popleft()

    if now in dic:
        for i in dic[now]:

            if p[i] == None:
                p[i] = now
                dep[i] = dep[now] + 1
                pnum[i] -= 1
                if pnum[i] == 0:
                    q.append(i)

            elif dep[i] < dep[now] + 1:
                p[i] = now
                dep[i] = dep[now] + 1
                pnum[i] -= 1
                if pnum[i] == 0:
                    q.append(i)
                

for i in range(N):

    print (p[i]+1)
Buggy python submission (verdict: Runtime Error):
N,H,W = map(int,input().split())

print ((N-H+1) * (N-W+1))

Fixed submission:
N=int(input())
H=int(input())
W=int(input())

print ((N-H+1) * (N-W+1))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A,B = map(int,input().split())

lis = []

P = list(map(int,input().split()))

for i in P:
  if i <= A:
    lis[0] += 1
  elif i <= B:
    lis[1] += 1
  else:
    lis[2] += 1
    
print (min(lis))

Fixed submission:
N = int(input())
A,B = map(int,input().split())

lis = [0,0,0]

P = list(map(int,input().split()))

for i in P:
  if i <= A:
    lis[0] += 1
  elif i <= B:
    lis[1] += 1
  else:
    lis[2] += 1
    
print (min(lis))
Buggy python submission (verdict: Time Limit Exceeded):

N,K = map(int,input().split())

h = list(map(int,input().split()))

lis = [0] + [float("inf")] * (N-1)

#print (lis)



for i in range(N-1):

    for j in range(K):

        j += 1

        if i + j < N :

            lis[i+j] = min( lis[i+j] , lis[i] + abs(h[i+j] - h[i]) )

print (lis[-1])


Fixed submission:

N,K = map(int,input().split())

h = list(map(int,input().split()))

lis = [0] + [float("inf")] * (N-1)

#print (lis)



for i in range(N-1):

    for j in range(K):

        j += 1

        if i + j < N :

            lis[i+j] = min( lis[i+j] , lis[i] + abs(h[i+j] - h[i]) )

print (lis[-1])