Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

def main():
    n = int(input())
    x = list(map(int, input().split()))
    ans = [0] * n
    for i in range(n):
        fix = x[0:i] + x[i + 1:n]
        fix.sort()
        ans[i] = fix[n // 2 - 1]
    print(*ans, sep='\n')


if __name__ == "__main__":
    main()


Fixed submission:
#!/usr/bin/env python3

def main():
    n = int(input())
    x = list(map(int, input().split()))
    ans = [0] * n
    x_sort = sorted(x)
    a = x_sort[1:n]
    a_med = a[n // 2 - 1]
    b = x_sort[0:n - 1]
    b_med = b[n // 2 - 1]
    for i in range(n):
        if x[i] < a_med:
            ans[i] = a_med
        else:
            ans[i] = b_med

    print(*ans, sep='\n')


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = [0] * n
    for i in range(n):
        fix = [0] + a[0:i] + a[i + 1:n] + [0]
        ans[i] = sum([abs(fix[j] - fix[j - 1]) for j in range(1, n + 1)])
    print(*ans, sep='\n')


if __name__ == "__main__":
    main()


Fixed submission:
#!/usr/bin/env python3

def main():
    n = int(input())
    a = [0] + list(map(int, input().split())) + [0]
    dist = [abs(a[i] - a[i - 1]) for i in range(1, n + 2)]
    total = sum(dist)
    ans = [0] * n
    for i in range(n):
        ans[i] = total - dist[i] - dist[i + 1] + abs(a[i] - a[i + 2])
    print(*ans, sep='\n')


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    blue = [int(input()) for i in range(int(input()))]
    red = [int(input()) for i in range(int(input()))]
    l = list(set(blue))
    print(max(0, max(blue.count(l[i]) - red.count(l[i]) for i in range(len(l)))))


if __name__ == "__main__":
    main()


Fixed submission:
#!/usr/bin/env python3

def main():
    blue = [input() for i in range(int(input()))]
    red = [input() for i in range(int(input()))]
    l = list(set(blue))
    print(max(0, max(blue.count(l[i]) - red.count(l[i]) for i in range(len(l)))))


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    P = map(int, input().split())
    cnt = 0
    for i in range(N):
        if P[i] == i + 1:
            cnt += 1
        ans = (cnt + 1) // 2
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N = int(input())
    P = list(map(int, input().split()))
    cnt = 0
    for i in range(N - 1):
        if P[i] == i + 1:
            cnt += 1
            P[i + 1], P[i] = P[i], P[i + 1]
    if P[N - 1] == N:
        cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

def main():
    n, m = map(int, input().split())
    ab = sorted([list(map(int, input().split())) for i in range(m)])
    ans = "IMPOSSIBLE"
    for i in range(m):
        if ab[i][0] == 1:
            if [ab[i][1], n] in ab[i + 1:]:
                ans = "POSSIBLE"
        else:
            break
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
#!/usr/bin/env python3

def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    ans = "IMPOSSIBLE"
    list_1 = []
    list_n = []
    for i in range(m):
        if ab[i][0] == 1:
            list_1.append(ab[i][1])
        elif ab[i][1] == n:
            list_n.append(ab[i][0])
    if len(set(list_1) & set(list_n)) > 0:
        ans = "POSSIBLE"
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    ans = "IMPOSSIBLE"
    for i in range(m):
        if ab[i][0] == 1:
            if [ab[i][1], n] in ab:
                ans = "POSSIBLE"
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
#!/usr/bin/env python3

def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    ans = "IMPOSSIBLE"
    list_1 = []
    list_n = []
    for i in range(m):
        if ab[i][0] == 1:
            list_1.append(ab[i][1])
        elif ab[i][1] == n:
            list_n.append(ab[i][0])
    if len(set(list_1) & set(list_n)) > 0:
        ans = "POSSIBLE"
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    a = input()
    b = input() + [""]
    for i in range(len(a)):
        print(a[i], end="")
        print(b[i], end="")


if __name__ == "__main__":
    main()


Fixed submission:
#!/usr/bin/env python3

def main():
    a = input()
    b = input()
    for i in range(len(a)):
        print(a[i], end="")
        if i < len(b):
            print(b[i], end="")
    print()


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
print(math.factorial(int(input())))

Fixed submission:
import math


def main():
    N = int(input())
    ans = math.factorial(N)
    mod = 10**9 + 7
    print(ans % mod)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    ans = 1
    mod = 10**9 + 7
    for i in range(1, N + 1):
        ans *= i
    print(ans % mod)


if __name__ == "__main__":
    main()


Fixed submission:
import math


def main():
    N = int(input())
    ans = math.factorial(N)
    mod = 10**9 + 7
    print(ans % mod)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    ans = 1
    mod = 10**9 + 7
    for i in range(1, N + 1):
        ans *= i
    print(ans % mod)


if __name__ == "__main__":
    main()


Fixed submission:
import math


def main():
    N = int(input())
    ans = math.factorial(N)
    mod = 10**9 + 7
    print(ans % mod)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    x, y = map(int, input().split())
    A = abs(abs(x) - abs(y))

    if x * y > 0:
        if x < y:
            B = 0
        else:
            B = 2
    elif x == 0:
        if x < y:
            B = 0
        else:
            B = 1
    elif y == 0:
        if x < y:
            B = 0
        else:
            B = 1

    print(A + B)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    x, y = map(int, input().split())
    A = abs(abs(x) - abs(y))

    if x * y > 0:
        if x < y:
            B = 0
        else:
            B = 2
    elif x == 0:
        if x < y:
            B = 0
        else:
            B = 1
    elif y == 0:
        if x < y:
            B = 0
        else:
            B = 1
    else:
        B = 1

    print(A + B)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N,X,M = map(int,input().split())

data = [X for i in range(M+1)]
val = set([X])

start = -1
period = -1
for i in range(1,M+1):
    data[i] = pow(data[i-1],2,M)
    if data[i] in val:
        for j in range(0,i):
            if data[j]==data[i]:
                start = j
                period = i-j
                break
    else:
        val.add(data[i])

if N<=M:
    print(sum(data[:N]))
else:
    res = sum(data[:start])

    backet = sum(data[start:start+period])
    Q = (N - start) // period
    R = (N- start) % period

    res += backet*Q + sum(data[start:start+R])
    print(res)

Fixed submission:
N,X,M = map(int,input().split())

data = [X for i in range(M+1)]
val = set([X])

start = -1
period = -1
for i in range(1,M+1):
    data[i] = pow(data[i-1],2,M)
    if data[i] in val:
        for j in range(0,i):
            if data[j]==data[i]:
                start = j
                period = i-j
                break
        break
    else:
        val.add(data[i])

if N<=M:
    print(sum(data[:N]))
else:
    res = sum(data[:start])

    backet = sum(data[start:start+period])
    Q = (N - start) // period
    R = (N- start) % period

    res += backet*Q + sum(data[start:start+R])
    print(res)
Buggy python submission (verdict: Runtime Error):
import sys

input = sys.stdin.readline

sys.setrecursionlimit(5*10**5)

N,M = map(int,input().split())
edge = [[] for i in range(M)]
rev_edge = [[] for i in range(M)]
for _ in range(M):
    a,b = map(int,input().split())
    edge[a].append(b)
    rev_edge[b].append(a)

seen = [False]*N
stop = []

def dfs(v):
    for nv in edge[v]:
        if not seen[nv]:
            seen[nv]=True
            dfs(nv)
    stop.append(v)

for i in range(N):
    if not seen[i]:
        seen[i] = True
        dfs(i)

seen = [False]*N

def scc():
    res = []
    connect = []
    def rev_dfs(v):
        for nv in rev_edge[v]:
            if not seen[nv]:
                connect.append(nv)
                seen[nv]=True
                rev_dfs(nv)

    while stop:
        while stop and seen[stop[-1]]:
            stop.pop()
        if not stop:
            break
        connect = [stop[-1]]
        seen[stop[-1]] = True
        rev_dfs(stop[-1])
        res.append(connect)
    return res

res = scc()
print(len(res))
for L in res:
    print(len(L),*L)


Fixed submission:
import sys

input = sys.stdin.readline

sys.setrecursionlimit(5*10**5)

N,M = map(int,input().split())
edge = [[] for i in range(N)]
rev_edge = [[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    edge[a].append(b)
    rev_edge[b].append(a)

seen = [False]*N
stop = []

def dfs(v):
    for nv in edge[v]:
        if not seen[nv]:
            seen[nv]=True
            dfs(nv)
    stop.append(v)

for i in range(N):
    if not seen[i]:
        seen[i] = True
        dfs(i)

seen = [False]*N

def scc():
    res = []
    connect = []
    def rev_dfs(v):
        for nv in rev_edge[v]:
            if not seen[nv]:
                connect.append(nv)
                seen[nv]=True
                rev_dfs(nv)

    while stop:
        while stop and seen[stop[-1]]:
            stop.pop()
        if not stop:
            break
        connect = [stop[-1]]
        seen[stop[-1]] = True
        rev_dfs(stop[-1])
        res.append(connect)
    return res

res = scc()
print(len(res))
for L in res:
    print(len(L),*L)
Buggy python submission (verdict: Runtime Error):
mycode = r'''
# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False, cdivision=True
ctypedef long long LL
from libc.stdio cimport scanf
from libc.vector cimport vector
ctypedef vector[LL] vec

cdef:
    LL N,M
    vec A

scanf("%lld %lld",N,M)
'''

import sys
import os
if sys.argv[-1] == 'ONLINE_JUDGE':  # コンパイル時
    with open('mycode.pyx', 'w') as f:
        f.write(mycode)
    os.system('cythonize -i -3 -b mycode.pyx')

import mycode

Fixed submission:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input=sys.stdin.readline


N,M=map(int,input().split())
uf=UnionFindVerSize(N)
for _ in range(M):
    a,b=map(int,input().split())
    uf.unite(a-1,b-1)

ans=-1
for i in range(N):
    ans=max(ans,uf.get_size(i))

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

N=int(input())
city=[]
for i in range(N):
    x,y,p=map(int,input().split())
    city.append((x,y,p))

xx=[[abs(city[j][0]) for j in range(N)] for i in range(2**N)]
yy=[[abs(city[j][1]) for j in range(N)] for i in range(2**N)]

for i in range(2**N):
    X=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            X.append(city[j][0])
            xx[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in X:
            res=min(res,abs(city[j][0]-k))
        xx[i][j]=res

for i in range(2**N):
    Y=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            Y.append(city[j][1])
            yy[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in Y:
            res=min(res,abs(city[j][1]-k))
        yy[i][j]=res

ans=[10**15 for i in range(N+1)]
for i in range(3**N):
    rest=i
    X=0
    Y=0
    count=0
    amari=[]
    for j in range(N):
        r=rest%3
        if r==1:
            count+=1
            X+=2**j
        elif r==2:
            count+=1
            Y+=2**j
        else:
            amari.append(j)
        rest//=3
    res=0
    for j in amari:
        x=xx[X][j]
        y=yy[Y][j]
        res+=min(x,y)*city[j][2]
    ans[count]=min(ans[count],res)

for i in range(N+1):
    print(ans[i])


Fixed submission:
import bisect

N=int(input())
city=[]
for i in range(N):
    x,y,p=map(int,input().split())
    city.append((x,y,p))

xx=[[abs(city[j][0]) for j in range(N)] for i in range(2**N)]
yy=[[abs(city[j][1]) for j in range(N)] for i in range(2**N)]

for i in range(2**N):
    X=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            X.append(city[j][0])
            xx[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in X:
            res=min(res,abs(city[j][0]-k))
        xx[i][j]=res

for i in range(2**N):
    Y=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            Y.append(city[j][1])
            yy[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in Y:
            res=min(res,abs(city[j][1]-k))
        yy[i][j]=res

ans=[10**15 for i in range(N+1)]
for i in range(2**N):
    cond=i
    rest=[j for j in range(N) if i>>j &1==0]
    count=N-len(rest)
    while True:
        X=cond
        Y=i-cond
        temp=0
        for j in rest:
            temp+=min(xx[X][j],yy[Y][j])*city[j][2]
        ans[count]=min(ans[count],temp)
        if cond==0:
            break
        else:
            cond=(cond-1)&i

for i in range(N+1):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
N=int(input())
X=input()

data=[0]*N
for i in range(1,N):
    temp=0
    for j in range(20):
        temp+=(i>>j &1)
    next=i%temp
    data[i]=data[next]+1

base=sum(int(X[i]) for i in range(N))

basedown=0
baseup=0
for i in range(N):
    basedown=(basedown*2)%(base-1)
    baseup=(baseup*2)%(base+1)
    basedown=(basedown+int(X[i]))%(base-1)
    baseup=(baseup+int(X[i]))%(base+1)

for i in range(N):
    if X[i]=="1":
        temp=(basedown-pow(2,N-1-i,base-1))%(base-1)
        print(1+data[temp])
    else:
        temp=(baseup+pow(2,N-1-i,base+1))%(base+1)
        print(1+data[temp])


Fixed submission:
N=int(input())
X=input()

data=[0]*N
for i in range(1,N):
    temp=0
    for j in range(20):
        temp+=(i>>j &1)
    next=i%temp
    data[i]=data[next]+1

base=sum(int(X[i]) for i in range(N))

if base==0:
    baseup=0
    for i in range(N):
        baseup=(baseup*2)%(base+1)
        baseup=(baseup+int(X[i]))%(base+1)

    for i in range(N):
        if X[i]=="1":
            temp=(basedown-pow(2,N-1-i,base-1))%(base-1)
            print(1+data[temp])
        else:
            temp=(baseup+pow(2,N-1-i,base+1))%(base+1)
            print(1+data[temp])
elif base==1:
    baseup=0
    for i in range(N):
        baseup=(baseup*2)%(base+1)
        baseup=(baseup+int(X[i]))%(base+1)

    for i in range(N):
        if X[i]=="1":
            print(0)
        else:
            temp=(baseup+pow(2,N-1-i,base+1))%(base+1)
            print(1+data[temp])
else:
    basedown=0
    baseup=0
    for i in range(N):
        basedown=(basedown*2)%(base-1)
        baseup=(baseup*2)%(base+1)
        basedown=(basedown+int(X[i]))%(base-1)
        baseup=(baseup+int(X[i]))%(base+1)

    for i in range(N):
        if X[i]=="1":
            temp=(basedown-pow(2,N-1-i,base-1))%(base-1)
            print(1+data[temp])
        else:
            temp=(baseup+pow(2,N-1-i,base+1))%(base+1)
            print(1+data[temp])
Buggy python submission (verdict: Time Limit Exceeded):
A,B,C,D=map(int,input().split())
mod=998244353
dp=[[[0 for k in range(2)] for i in range(D+1)] for i in range(C+1)]
dp[C][D][0]=1
dp[C][D][1]=1
for i in range(D-1,B-1,-1):
    dp[C][i][0]=(dp[C][i+1][1]*C)%mod
    dp[C][i][1]=(dp[C][i+1][1]*C)%mod
for j in range(C-1,A-1,-1):
    dp[j][D][0]=(dp[j+1][D][0]*D)%mod
    dp[j][D][1]=(dp[j+1][D][0])%mod

for i in range(C-1,A-1,-1):
    for j in range(D-1,B-1,-1):
        dp[i][j][0]=(dp[i+1][j][0]*j+dp[i][j+1][1]*i)%mod
        dp[i][j][1]=(dp[i+1][j][0]+dp[i][j+1][1]*i)%mod

print(dp[A][B][0])


Fixed submission:
A,B,C,D=map(int,input().split())
mod=998244353
dpx=[[0 for i in range(D+1)] for j in range(C+1)]
dpy=[[0 for i in range(D+1)] for j in range(C+1)]
dpx[C][D]=1
dpy[C][D]=1
for i in range(D-1,B-1,-1):
    dpx[C][i]=(dpy[C][i+1]*C)%mod
    dpy[C][i]=(dpy[C][i+1]*C)%mod
for j in range(C-1,A-1,-1):
    dpx[j][D]=(dpx[j+1][D]*D)%mod
    dpy[j][D]=(dpx[j+1][D])%mod

for i in range(C-1,A-1,-1):
    for j in range(D-1,B-1,-1):
        dpx[i][j]=((dpx[i+1][j]*j)%mod+(dpy[i][j+1]*i)%mod)%mod
        dpy[i][j]=(dpx[i+1][j]+(dpy[i][j+1]*i)%mod)%mod

print(dpx[A][B])
Buggy python submission (verdict: Runtime Error):
A,V=map(int,input().split())
B,W=map(int,input().split())
T=input()
if B>=A:
    print("YES" if A+V*T>=B+W*T else "NO")
else:
    print("YES" if B-W*T>=A-V*T else "NO") 


Fixed submission:
A,V=map(int,input().split())
B,W=map(int,input().split())
T=int(input())
if B>=A:
    print("YES" if A+V*T>=B+W*T else "NO")
else:
    print("YES" if B-W*T>=A-V*T else "NO")
Buggy python submission (verdict: Time Limit Exceeded):
def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2

S=input()
N=len(S)
mod=2019
data=[(int(S[-i-1])*pow(10,i)) for i in range(0,N)]

for i in range(1,N):
    data[i]+=data[i-1]
    data[i]%=mod

data=[0]+data
data.sort()
print(equalfind(data))

Fixed submission:
def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2

S=input()
N=len(S)
mod=2019
data=[(int(S[-i-1])*pow(10,i,mod)) for i in range(0,N)]

for i in range(1,N):
    data[i]+=data[i-1]
    data[i]%=mod

data=[0]+data
data.sort()
print(equalfind(data))
Buggy python submission (verdict: Time Limit Exceeded):
mod = 998244353
omega = pow(3,119,mod)
rev_omega = pow(omega,mod-2,mod)

N = 2*10**5
g1 = [1]*(N+1) # 元テーブル
g2 = [1]*(N+1) #逆元テーブル
inv = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inv[i]=( ( -inv[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inv[i]) % mod )
inv[0]=0

def _ntt(f,L,reverse=False):
    F=[f[i] for i in range(L)]
    n = L.bit_length() - 1
    base = omega
    if reverse:
        base = rev_omega

    if not n:
        return F

    size = 2**n
    wj = pow(base,2**22,mod)
    res = [0]*2**n

    for i in range(n,0,-1):
        use_omega = pow(base,2**(22+i-n),mod)
        res = [0]*2**n
        size //= 2
        w = 1
        for j in range(0,L//2,size):
            for a in range(size):
                res[a+j] = (F[a+2*j] + w * F[a+size+2*j]) % mod
                t = (w * wj) % mod
                res[L//2+a+j] = (F[a+2*j] + t * F[a+size+2*j]) % mod
            w = (w * use_omega) % mod
        F = res

    return res

def ntt(f,L=0):
    l = len(f)
    if not L:
        L = 1<<((l-1).bit_length())
    while len(f)<L:
        f.append(0)
    f=f[:L]
    F = _ntt(f,L)
    return F

def intt(f,L=0):
    l = len(f)
    if not L:
        L = 1<<((l-1).bit_length())
    while len(f)<L:
        f.append(0)
    f=f[:L]
    F = _ntt(f,L,reverse=True)
    inv = pow(L,mod-2,mod)
    for i in range(L):
        F[i] *= inv
        F[i] %= mod
    return F

def convolve(f,g,limit):
    l = len(f)+len(g)-1
    L = 1<<((l-1).bit_length())

    F = ntt(f,L)
    G = ntt(g,L)

    H = [(F[i] * G[i]) % mod for i in range(L)]

    h = intt(H,L)

    return h[:limit]

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

prod = [0]
res = 0
for i in range(N):
    poly = [0 for i in range(A[i]+1)]
    poly[-1] = 1
    poly[0] = 1
    prod[0] = (prod[0] + 1) % mod
    prod = convolve(prod,poly,S+1)
    if len(prod)==S+1:
        res += prod[S]
        res %= mod
print(res)

Fixed submission:
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353

dp=[[0 for i in range(0,S+1)] for j in range(0,N)]
for i in range(0,S+1):
    if i==A[0]:
        dp[0][i]=1

for i in range(1,N):
    for j in range(0,S+1):
        if j>A[i]:
            dp[i][j]=(dp[i-1][j]+dp[i-1][j-A[i]])%mod
        elif j==A[i]:
            dp[i][j]=(dp[i-1][j]+(i+1))%mod
        else:
            dp[i][j]=dp[i-1][j]

ans=0
for i in range(0,N):
    ans=(ans+dp[i][S])%mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2


N,P=map(int,input().split())
S=input()
if P!=2 and P!=5:
    data=[(int(S[i])*(10**(N-i-1)))%P for i in range(0,N)]
    ans=list(accumulate(data))
    ans=[ans[i]%P for i in range(0,N)]
    ans.append(0)
    print(equalfind(ans))
elif P==2:
    ans=0
    for i in range(0,N):
        if int(S[i])%2==0:
            ans+=i+1
    print(ans)
else:
    ans=0
    for i in range(0,N):
        if int(S[i])%5==0:
            ans+=i+1
    print(ans)


Fixed submission:
from itertools import accumulate

def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2

N,P=map(int,input().split())
S=input()

def pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = (ans*x)%P
    x = (x*x)%P
    n = n >> 1 #ビットシフト
  return ans%P

if P!=2 and P!=5:
    data=[(int(S[i])*(pow(10,N-1-i)))%P for i in range(0,N)]
    ans=list(accumulate(data))
    ans=[ans[i]%P for i in range(0,N)]
    ans.append(0)
    print(equalfind(ans))
elif P==2:
    ans=0
    for i in range(0,N):
        if int(S[i])%2==0:
            ans+=i+1
    print(ans)
else:
    ans=0
    for i in range(0,N):
        if int(S[i])%5==0:
            ans+=i+1
    print(ans)