Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n,m=map(int, input().split())
xs = []
for _ in range(m):
    L, R, C = map(int, input().split())
    xs.append((L-1, R-1, C))
xs.sort()

mx = 10**15
ss = SegTree([0] + [mx] * n, n+1, mx, min)
for l, r, c in xs:
    mm = ss.query(l, n+1)
    nx = min(mm + c, ss.query(r, r+1))
    ss.update(r, nx)
r = ss.query(n-1,n)
print(r if r != mx else -1)


Fixed submission:
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n,m=map(int, input().split())
xs = []
for _ in range(m):
    L, R, C = map(int, input().split())
    xs.append((L-1, R-1, C))
xs.sort()

mx = 10**15
ss = SegTree([0] + [mx] * n, n+1, mx, min)
for l, r, c in xs:
    mm = ss.query(l, n+1)
    nx = min(mm + c, ss.query(r, r+1))
    ss.update(r, nx)
r = ss.query(n-1,n)
print(r if r != mx else -1)
Buggy python submission (verdict: Runtime Error):
from math import atan,degrees
a,b,x = map(int,input().split())
if a*a*b < 2*x:
    print(90-degrees(atan(a**3/(2*(a**2*b-x)))))
else:
    print(90-degrees(atan((2*x)/(a*b**2))))


Fixed submission:
from math import atan,degrees
a,b,x = map(int,input().split())
if a*a*b < 2*x:
    print(degrees(atan((2*(a**2*b-x))/a**3)))
else:
    print(degrees(atan((a*b**2)/(2*x))))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from copy import deepcopy

def main():
    INF = 10**18
    input = sys.stdin.readline
    N, M, L = [int(x) for x in input().split()]
    d = [set() for _ in range(N+1)]
    cs = [[INF] * (N+1) for _ in range(N+1)]
    for _ in range(M):
        A, B, C = [int(x) for x in input().split()]
        d[A].add(B)
        d[B].add(A)
        cs[A][B] = C
        cs[B][A] = C

    #ds = [[INF] * (N+1) for in range(N+1)]:
    ds = deepcopy(cs)
    bs = [[INF] * (N+1) for _ in range(N+1)]
    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(1, N+1):
                ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])
                if ds[i][j] <= L:
                    bs[i][j] = 1

    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(1, N+1):
                bs[i][j] = min(bs[i][j], bs[i][k] + bs[k][j])

    Q, = [int(x) for x in input().split()]
    for _ in range(Q):
        s, t = [int(x) for x in input().split()]
        print(bs[s][t]-1 if bs[s][t] < INF else -1)


if __name__ == '__main__':
    main()



Fixed submission:
import sys
from copy import deepcopy

def main():
    INF = 10**18
    input = sys.stdin.readline
    N, M, L = [int(x) for x in input().split()]
    d = [set() for _ in range(N+1)]
    ds = [[INF] * (N+1) for _ in range(N+1)]
    bs = [[INF] * (N+1) for _ in range(N+1)]
    for _ in range(M):
        A, B, C = [int(x) for x in input().split()]
        A, B = sorted([A, B])
        d[A].add(B)
        if L >= C:
            ds[A][B] = C

    nes = set()
    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(i+1, N+1):
                ds[i][j] = min(ds[i][j], ds[min(i, k)][max(i, k)] + ds[min(k, j)][max(k, j)])
                if ds[i][j] <= L:
                    bs[i][j] = 1

    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(i+1, N+1):
                bs[i][j] = min(bs[i][j], bs[min(i, k)][max(i, k)] + bs[min(k, j)][max(k, j)])

    Q, = [int(x) for x in input().split()]
    for _ in range(Q):
        s, t = sorted(int(x) for x in input().split())
        print(bs[s][t]-1 if bs[s][t] < INF else -1)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
MOD = 998244353

def zeta_gcd(a,primes):
    n = len(a)-1
    for p in primes:
        for i in range(n//p,0,-1):
            a[i] += a[p*i]
            a[i] %= MOD
def mobius_gcd(a,primes):
    n = len(a)
    for p in primes:
        for i in range(1,n):
            if i*p >= n: break
            a[i] -= a[p*i] 
            a[i] %= MOD
def get_primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

NNN = 10**6
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )

N, = map(int, input().split())
X = list(map(int, input().split()))
primes = get_primes(NNN)
fs = [0]*NNN
for x in X:
    fs[x] += x
#print(fs)
zeta_gcd(fs, primes)
#print(fs)
for i, x in enumerate(fs):
    fs[i] = x**2
#print(fs)
mobius_gcd(fs, primes)
#print(fs)
r = 0
for i, f in enumerate(fs[1:]):
    i += 1
    r = (r + f*inverse[i]) % MOD
for x in X:
    r = (r - x) % MOD

print((r*inverse[2])%MOD)


Fixed submission:
MOD = 998244353

def zeta_gcd(a,primes):
    n = len(a)-1
    for p in primes:
        for i in range(n//p,0,-1):
            a[i] += a[p*i]
            a[i] %= MOD
def mobius_gcd(a,primes):
    n = len(a)
    for p in primes:
        for i in range(1,n):
            if i*p >= n: break
            a[i] -= a[p*i] 
            a[i] %= MOD
def get_primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

NNN = 10**6 + 1
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )

N, = map(int, input().split())
X = list(map(int, input().split()))
primes = get_primes(NNN)
fs = [0]*NNN
for x in X:
    fs[x] += x
#print(fs)
zeta_gcd(fs, primes)
#print(fs)
for i, x in enumerate(fs):
    fs[i] = x**2
#print(fs)
mobius_gcd(fs, primes)
#print(fs)
r = 0
for i, f in enumerate(fs[1:]):
    i += 1
    r = (r + f*inverse[i]) % MOD
for x in X:
    r = (r - x) % MOD

print((r*inverse[2])%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input()) + 1
S = " "+input()
d = [[0]*N for _ in range(N)]
r = 0
for i in range(N):
    for j in range(i-1,0,-1):
        d[i][j] = d[i-1][j-1] + 1 if S[i] == S[j] else 0
        r = max(r, min(d[i][j], i-j))
print(r)


Fixed submission:
N = int(input()) + 1
S = " "+input()
d = [[0]*N for _ in range(N)]
r = 0
for i in range(N):
    for j in range(i-1,0,-1):
        d[i][j] = d[i-1][j-1] + 1 if S[i] == S[j] else 0
        r = max(r, min(d[i][j], i-j))
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
N=int(input())
xs = [None]
for _ in range(N):
    xs.append(list(map(int, input().split()))[::-1])
tops = [None] * (N+1)
for i in range(N):
    i += 1
    tops[i] = xs[i].pop()

cc = 0
rr = 0
while True:
    vs = set()
    nn = False
    for i in range(N):
        i += 1
        j = tops[i]
        if j == None:
            continue
        if i in vs or j in vs:
            continue
        if tops[j] == i:
            nn = True
            if len(xs[i]):
                tops[i] = xs[i].pop()
            else:
                tops[i] = None
                cc += 1
            if len(xs[j]):
                tops[j] = xs[j].pop()
            else:
                tops[j] = None
                cc += 1
            vs.add(i)
            vs.add(j)
    rr += 1
    if cc == N:
        break
    if not nn:
        rr = -1
        break

print(rr)


Fixed submission:
import sys
input = sys.stdin.readline
N=int(input())
xs = [None]
for _ in range(N):
    xs.append(list(map(int, input().split()))[::-1])
tops = [None] * (N+1)
for i in range(N):
    i += 1
    tops[i] = xs[i].pop()

cc = 0
rr = 0
ns = [i+1 for i in range(N)]
while True:
    vs = set()
    nn = False
    nns = []
    for i in ns:
        j = tops[i]
        if j == None:
            continue
        if i in vs or j in vs:
            continue
        if tops[j] == i:
            nn = True
            if len(xs[i]):
                tops[i] = xs[i].pop()
            else:
                tops[i] = None
                cc += 1
            if len(xs[j]):
                tops[j] = xs[j].pop()
            else:
                tops[j] = None
                cc += 1
            vs.add(i)
            vs.add(j)
            nns.append(i)
            nns.append(j)
    ns = nns
    rr += 1
    if cc == N:
        break
    if not nn:
        rr = -1
        break

print(rr)
Buggy python submission (verdict: Runtime Error):
n=int(input())
for i in range(N):
    i = i + 1
    for j in range(N-i):
        j = i+j+1
        for k in range(9):
            if i % (2**(k+1)) != j % (2**(k+1)):
                print(k+1, end=" ")
                break
    print()


Fixed submission:
N=int(input())
for i in range(N):
    i = i + 1
    for j in range(N-i):
        j = i+j+1
        for k in range(9):
            if i % (2**(k+1)) != j % (2**(k+1)):
                print(k+1, end=" ")
                break
    print()
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
G = [set() for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].add(b)
    G[b].add(a)

g2 = [set() for _ in range(N+1)]
p = [0]*(N+1)
vs = set()
stack = [1]
dfs_vs = []
vs.add(1)
while stack:
    v = stack.pop()
    dfs_vs.append(v)
    for u in G[v]:
        if u in vs:
            continue
        g2[v].add(u)
        p[u] = v
        stack.append(u)
        vs.add(u)

d = [0]*(N+1)
for i in range(Q):
    z, x = map(int, input().split())
    d[z] += x

#print(d)
#print(p)

for v in dfs_vs:
    d[v] += d[p[v]]

print(*d[1:])


Fixed submission:
import sys
sys.setrecursionlimit(300000)
input = sys.stdin.readline
n,q=map(int,input().strip().split())
d=[[] for _ in range(n)]

for _ in range(n-1):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)
l=[0]*n
for _ in range(q):
    a,b=map(int,input().split())
    l[a-1]+=b
rs=[0]*n

def rr(pa,s,dd,d):
    for c in d[s]:
        if c == pa:
            continue
        rs[c]=l[c]+dd
#        print(c,rs[c],dd)
        rr(s,c,dd+l[c],d)

s,dd=0,l[0]
rs[0] = l[0]
rr(None,s,dd,d)
for r in rs:
    print(r)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
n,q=map(int,input().strip().split())
d=[[] for _ in range(n)]

for _ in range(n-1):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)
l=[0]*n
for _ in range(q):
    a,b=map(int,input().split())
    l[a-1]+=b
rs=[0]*n

def rr(pa,s,dd,d):
    for c in d[s]:
        if c == pa:
            continue
        rs[c]=l[c]+dd
#        print(c,rs[c],dd)
        rr(s,c,dd+l[c],d)

s,dd=0,l[0]
rs[0] = l[0]
rr(None,s,dd,d)
for r in rs:
    print(r)


Fixed submission:
import sys
sys.setrecursionlimit(300000)
input = sys.stdin.readline
n,q=map(int,input().strip().split())
d=[[] for _ in range(n)]

for _ in range(n-1):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)
l=[0]*n
for _ in range(q):
    a,b=map(int,input().split())
    l[a-1]+=b
rs=[0]*n

def rr(pa,s,dd,d):
    for c in d[s]:
        if c == pa:
            continue
        rs[c]=l[c]+dd
#        print(c,rs[c],dd)
        rr(s,c,dd+l[c],d)

s,dd=0,l[0]
rs[0] = l[0]
rr(None,s,dd,d)
for r in rs:
    print(r)
Buggy python submission (verdict: Runtime Error):
k = int(input())
x, y = [int(x) for x in input().strip().split(" ")]
x, y = x-y, x+y

def main():
    if k % 2 == 0:
        if x % 2 != 0:
            return -1
    return to(x,y)

def cc(x, xs):
        if abs(x-xs) <= 2*k:
            if abs(x+k-xs) % 2 == k % 2:
                if abs(x+k-xs) <= abs(x-k-xs):
                    xs = x+k
                else:
                    xs = x-k
                return (True,xs)
            else:
                if x > xs:
                    xs += k
                else:
                    xs -= k
        else:
            if x > xs:
                xs += k
            else:
                xs -= k
        return (False,xs)


def to(x, y):
    rs = []
    xs, ys = 0, 0
    while True:
        if abs(x-xs) == k or abs(y-ys) == k:
            if abs(x-xs) <= k and abs(y-ys) <= k:
                return rs + [(x, y)]
        mm, ys = cc(y, ys)
        if mm:
            if x > xs:
                xs += k
            else:
                xs -= k
        else:
            mm, xs = cc(x, xs)
        rs.append((xs, ys))

if __name__ == '__main__':
    jj = main()
    if jj == -1:
        print(-1)
    else:
        print(len(jj))
        for r in jj:
            print((r[0]+r[1])//2, (r[1]-r[0])//2)




Fixed submission:
a, b = map(int, input().split())
if a%2 == b%2:
    print((a+b)//2)
else:
    print("IMPOSSIBLE")
Buggy python submission (verdict: Time Limit Exceeded):
S = input().strip()
mod = 10**9+7
n = len(S)
d = [[0]*13 for _ in range(n+1)]
d[n][0] = 1
S = S[::-1]
for i in range(n):
    i = n-i-1
    b = (10**i) % 13
    if S[i] == "?":
        for j in range(10):
            for k in range(13):
                d[i][(k+(j*b))%13] += d[i+1][k]
                d[i][(k+(j*b))%13] %= mod
    else:
        for k in range(13):
            d[i][(k+(int(S[i])*b))%13] += d[i+1][k]
            d[i][(k+(int(S[i])*b))%13] %= mod
print(d[0][5])


Fixed submission:
S = input().strip()[::-1]
mod = 10**9+7
n = len(S)
d = [[0]*13 for _ in range(n+1)]
d[0][0] = 1
b = 1
for i in range(n):
    for k in range(13):
        for j in range(10) if S[i] == "?" else [int(S[i])]:
            d[i+1][(k+(j*b))%13] += d[i][k]
            d[i+1][(k+(j*b))%13] %= mod
    b = b*10%13
print(d[n][5])

Buggy python submission (verdict: Time Limit Exceeded):
S = input().strip()
mod = 10**9+7
n = len(S)
d = [[0]*13 for _ in range(n+1)]
d[n][0] = 1
S = S[::-1]
for i in range(n):
    i = n-i-1
    b = (10**i) % 13
    if S[i] == "?":
        for j in range(10):
            for k in range(13):
                d[i][(k+(j*b))%13] += d[i+1][k]
                d[i][(k+(j*b))%13] %= mod
    else:
        for k in range(13):
            d[i][(k+(int(S[i])*b))%13] += d[i+1][k]
            d[i][(k+(int(S[i])*b))%13] %= mod
print(d[0][5])


Fixed submission:
S = input().strip()[::-1]
mod = 10**9+7
n = len(S)
d = [[0]*13 for _ in range(n+1)]
d[0][0] = 1
b = 1
for i in range(n):
    for k in range(13):
        for j in range(10) if S[i] == "?" else [int(S[i])]:
            d[i+1][(k+(j*b))%13] += d[i][k]
            d[i+1][(k+(j*b))%13] %= mod
    b = b*10%13
print(d[n][5])
Buggy python submission (verdict: Runtime Error):
Q,E,v,m=input,exec,[],10**9+7;N,K=map(int,Q().split());from collections import Counter as C;E("v+=Q().split();"*(N-1)+"g,v,r=list(C(v).values()),0,K*(K-1);"+"E(\"i=0;\"+\"r=(r*(K-2-i))%m;i+=1;\"*(g[v]-1));v+=1;"*N);print(r)


Fixed submission:
import sys
mod = 1000000007

sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
N, K = map(int, readline().split())

def P(x, y):
    r = 1
    for i in range(y):
        r = (r * (x - i)) % mod
    return r

G = [[] for _ in range(N)]
for v in range(N-1):
    a, b = map(int, readline().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)

def dfs(bb, v):
    cn = 0
    r = 1
    for u in G[v]:
        if u == bb:
            continue
        cn += 1
        r = (r * dfs(v, u)) % mod
    if cn == 0:
        return 1
    else:
        if bb == None:
            return P(K-1, cn) * r % mod
        else:
            return P(K-2, cn) * r % mod

print((K*dfs(None, 0))%mod)

Buggy python submission (verdict: Runtime Error):
Q,E,v,m=input,exec,[],10**9+7;N,K=map(int,Q().split());from collections import Counter as C;E("v+=Q().split();"*(N-1)+"g,v,r=list(C(v).values()),0,K*(K-1);"+"E(\"i=0;\"+\"r=(r*(K-2-i))%m;i+=1;\"*(g[v]-1));v+=1;"*N);print(r)

Fixed submission:
import sys
mod = 1000000007

sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
N, K = map(int, readline().split())

def P(x, y):
    r = 1
    for i in range(y):
        r = (r * (x - i)) % mod
    return r

G = [[] for _ in range(N)]
for v in range(N-1):
    a, b = map(int, readline().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)

def dfs(bb, v):
    cn = 0
    r = 1
    for u in G[v]:
        if u == bb:
            continue
        cn += 1
        r = (r * dfs(v, u)) % mod
    if cn == 0:
        return 1
    else:
        if bb == None:
            return P(K-1, cn) * r % mod
        else:
            return P(K-2, cn) * r % mod

print((K*dfs(None, 0))%mod)
Buggy python submission (verdict: Runtime Error):

N, M = [int(x) for x in input().strip().split(" ")]

vs = set()
def dfs_w(v, d, t):
    # dfs while版 
    r = -1
    stack = [v]
    path = []
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v < 0:
            path.pop()
        else:
            path.append(v)
            vs.add(v)
            for u in d[v]:
                if u == t:
                    if r != -1:
                        r = min(len(path)//3, r)
                    else:
                        r = len(path)//3
                if u in vs:
                    continue
                stack += [-v, u]
    return r

d = [set() for _ in range(3*N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(N+b)
    d[N+a].add(2*N+b)
    d[2*N+a].add(b)

s, t = [int(x) for x in input().strip().split(" ")]
print(dfs_w(s, d, t))


Fixed submission:
s = input().strip()
from collections import defaultdict
d = defaultdict(int)
for c in s:
    d[c] += 1
for k in d:
    if d[k] != 2:
        print("No")
        break
else:
    print("Yes")
Buggy python submission (verdict: Runtime Error):
N, M = [int(x) for x in input().strip().split(" ")]

vs = set()
def dfs_w(v, d, t):
    # dfs while版 
    r = -1
    stack = [v]
    path = []
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v < 0:
            path.pop()
        else:
            path.append(v)
            vs.add(v)
            for u in d[v]:
                if u == t:
                    if r != -1:
                        r = min(len(path)//3, r)
                    else:
                        r = len(path)//3
                    continue
                if u in vs:
                    continue
                stack += [-v, u]
    return r

d = [set() for _ in range(3*N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(N+b)
    d[N+a].add(2*N+b)
    d[2*N+a].add(b)

s, t = [int(x) for x in input().strip().split(" ")]
print(dfs_w(s, d, t))


Fixed submission:
n, k = [int(x) for x in input().strip().split(" ")]
m=~-n*(n-2)//2
if k>m:
    print(-1)
else:
    m-=k
    print(m+n-1)
    for i in range(1, n):
        print(i, n)
    for i in range(1, n):
        for j in range(i+1, n):
            if m==0:
                break
            print(i, j)
            m-=1
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = d[i][j+1] + d[i+1][j] - (ss[i] != ts[j])*d[i][j]
print(d[n][m]%(10**9+7))


Fixed submission:
n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = (d[i][j+1] + d[i+1][j] - (ss[i] != ts[j])*d[i][j]) % (10**9+7)
print(d[n][m])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = d[i][j+1] + d[i+1][j] - (0 if ss[i] == ts[j] else d[i][j])
print(d[n][m]%(10**9+7))


Fixed submission:
n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = (d[i][j+1] + d[i+1][j] - (ss[i] != ts[j])*d[i][j]) % (10**9+7)
print(d[n][m])

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = d[i][j+1] + d[i+1][j] - (0 if ss[i] == ts[j] else d[i][j])
print(d[n][m]%(10**9+7))


Fixed submission:
n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = (d[i][j+1] + d[i+1][j] - (ss[i] != ts[j])*d[i][j]) % (10**9+7)
print(d[n][m])
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
dp = [1]*(N+1)
for _ in range(M):
    a, = map(int, input().split())
    dp[a] = 0
    A.append(a)
for i in range(2,N+1):
    if dp[i] != 0:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[N])


Fixed submission:
N, M = map(int, input().split())
mod=10**9+7
dp = [1]*(N+1)
for _ in range(M):
    a, = map(int, input().split())
    dp[a] = 0
for i in range(2,N+1):
    if dp[i] != 0:
        dp[i] = (dp[i-1] + dp[i-2])%mod
print(dp[N])