Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N=int(input())
XYU=[tuple(input().split()) for _ in range(N)]
U=[]
R=[]
D=[]
L=[]
for x,y,u in XYU:
 x,y = int(x),int(y)
 if u=="U":
  U.append((x,y))
 elif u=="D":
  D.append((x,y))
 elif u=="L":
  L.append((x,y))
 else:
  R.append((x,y))
r=10**9
def z(A):
 global r
 A.sort()
 n=p=-10**9
 for k,c,a in A:
  if k!=n:
   if a==1:
    n=k
    p=c
   continue
  if a==1:
   p=c
   continue
  if (c-p)*5<ans:
   ans=(c-p)*5
z([(x,y,1) for x,y in U]+[(x,y,-1) for x,y in D])
z([(y,x,1) for x,y in R]+[(y,x,-1) for x,y in L])
z([(x+y,x-y,1) for x,y in R]+[(x+y,x-y,-1) for x,y in U])
z([(x+y,x-y,1) for x,y in D]+[(x+y,x-y,-1) for x,y in L])
z([(x-y,x+y,1) for x,y in U]+[(x-y,x+y,-1) for x,y in L])
z([(x-y,x+y,1) for x,y in R]+[(x-y,x+y,-1) for x,y in D])
print("SAFE" if r>=10**9 else r)

Fixed submission:
def get_collision(A,ans):
    A.sort()
    nowkey = -10**10
    prevcoor = -10**10
    ret = ans[0]
    for key, coor, a in A:
        if key != nowkey:
            if a == 1:
                nowkey = key
                prevcoor = coor
                continue
            else:
                continue
        if a == 1:
            prevcoor = coor
            continue
        if (coor - prevcoor)*5 < ret:
            ret = (coor - prevcoor)*5
    ans[0] = ret

def main():
    N = int( input())
    XYU = [ tuple( input().split()) for _ in range(N)]
    U = []
    R = []
    D = []
    L = []
    for x, y, u in XYU:
        x, y = int(x), int(y)
        if u == "U":
            U.append((x,y))
        elif u == "D":
            D.append((x,y))
        elif u == "L":
            L.append((x,y))
        else:
            R.append((x,y))
    ans = [10**10]

    UD = [(x,y,1) for x, y in U] + [(x,y,-1) for x, y in D]
    get_collision(UD, ans)
    LR = [(y,x,1) for x, y in R] + [(y,x,-1) for x, y in L]
    get_collision(LR, ans)
    RU = [(x+y,x-y,1) for x, y in R] + [(x+y,x-y,-1) for x,y in U]
    get_collision(RU, ans)
    LD = [(x+y,x-y,1) for x, y in D] + [(x+y,x-y,-1) for x,y in L]
    get_collision(LD,ans)
    LU = [(x-y,x+y,1) for x,y in U] + [(x-y,x+y,-1) for x,y in L]
    get_collision(LU,ans)
    RD = [(x-y,x+y,1) for x,y in R] + [(x-y,x+y,-1) for x,y in D]
    get_collision(RD,ans)
    if ans[0] < 10**10:
        print(ans[0])
    else:
        print("SAFE")
        
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#import sys
#input = sys.stdin.readline
from collections import Counter
def func(x):
    cnt = 0
    y = x
    while x > 0:
        if x%2 == 1:
            cnt += 1
        x //= 2
    return y%cnt
        
def main():
    N = int( input())
    X = list( map( int, list( input())))
    base_plus = 0
    base_minus = 0
    r = 1
    one = Counter(X)[1]
    for x in X[::-1]:
        base_plus += r*x
        base_plus %= one+1
        r *= 2
        r %= one+1
    r = 1
    for x in X[::-1]:
        base_minus += r*x
        base_minus %= one-1
        r *= 2
        r %= one-1

    ANS = [0]*N
    # print(base)
    # print(bin(base))
    for i in range(N):
        if one == 1:
            if X[i] == 1:
                ANS[i] = 0
                continue
        if X[i] == 1:
            xi = (base_minus -  pow(2,N-1-i,one-1))%(one-1)
            # print(i, bin(base -  pow(2,N-1-i)), one-1)
        else:
            xi = (base_plus +  pow(2,N-1-i,one+1))%(one+1)
            # print(i, bin(base +  pow(2,N-1-i)), one+1)
        # print(i,xi)
        if xi == 0:
            ANS[i] = 1
            continue
        ans = 1
        while xi > 0:
            ans += 1
            xi = func(xi)
        ANS[i] = ans
    print("\n".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()


Fixed submission:
#import sys
#input = sys.stdin.readline
from collections import Counter
def func(x):
    cnt = 0
    y = x
    while x > 0:
        if x%2 == 1:
            cnt += 1
        x //= 2
    return y%cnt
        
def main():
    N = int( input())
    X = list( map( int, list( input())))
    base_plus = 0
    base_minus = 0
    r = 1
    one = Counter(X)[1]
    for x in X[::-1]:
        base_plus += r*x
        base_plus %= one+1
        r *= 2
        r %= one+1
    r = 1
    if one > 1:
        for x in X[::-1]:
            base_minus += r*x
            base_minus %= one-1
            r *= 2
            r %= one-1

    ANS = [0]*N
    # print(base)
    # print(bin(base))
    for i in range(N):
        if one == 1:
            if X[i] == 1:
                ANS[i] = 0
                continue
        if X[i] == 1:
            xi = (base_minus -  pow(2,N-1-i,one-1))%(one-1)
            # print(i, bin(base -  pow(2,N-1-i)), one-1)
        else:
            xi = (base_plus +  pow(2,N-1-i,one+1))%(one+1)
            # print(i, bin(base +  pow(2,N-1-i)), one+1)
        # print(i,xi)
        if xi == 0:
            ANS[i] = 1
            continue
        ans = 1
        while xi > 0:
            ans += 1
            xi = func(xi)
        ANS[i] = ans
    print("\n".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
Q = 998244353
#import sys
#input = sys.stdin.readline
def main():
    A, B, C, D = map( int, input().split())
    dp = [[0]*3002 for _ in range(3001)]
    dp[C][D] = 1
    for a in range(C-1,A-1,-1):
        dp[a][D] = dp[a+1][D]*D%Q
    for b in range(D-1,B-1,-1):
        dp[C][b] = dp[C][b+1]*C%Q
    for a in range(C-1,A-1,-1):
        z = dp[a+1][D]*a%Q
        for b in range(D-1,B-1,-1):
            dp[a][b] = (b*dp[a+1][b] + z)%Q
            z = (z + dp[a+1][b])*a%Q
    # for i in range(C+1):
    #     print(dp[i][:D+1])
    print(dp[A][B])
if __name__ == '__main__':
    main()


Fixed submission:
Q = 998244353
#import sys
#input = sys.stdin.readline
def main():
    A, B, C, D = map( int, input().split())
    dp = [[0]*3002 for _ in range(3001)]
    dp[C][D] = 1
    for a in range(C-1,A-1,-1):
        dp[a][D] = dp[a+1][D]*D%Q
    for b in range(D-1,B-1,-1):
        dp[C][b] = dp[C][b+1]*C%Q
    for a in range(C-1,A-1,-1):
        z = dp[a+1][D]*a%Q
        for b in range(D-1,B-1,-1):
            dp[a][b] = (b*dp[a+1][b] + z)%Q
            z = (z + dp[a+1][b])*a%Q
    # for i in range(C+1):
    #     print(dp[i][:D+1])
    print(dp[A][B])
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#import sys
#input = sys.stdin.readline
from itertools import accumulate
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    for i in range(K):
        B = [0]*(N+1)
        for j in range(N):
            d = A[j]
            x = j-d
            y = j+d
            if x < 0:
                B[0] += 1
            else:
                B[x] += 1
            if N-1 < y:
                B[N] -= 1
            else:
                B[y+1] -= 1
        A = list( accumulate(B))
        check = True
        for j in range(N):
            if A[j] < N:
                check = False
        if check:
            break
    print(" ".join( map(str, A[:-1])))
            
                
        
if __name__ == '__main__':
    main()


Fixed submission:
#import sys
#input = sys.stdin.readline
from itertools import accumulate
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    for i in range(K):
        B = [0]*(N+1)
        for j in range(N):
            d = A[j]
            x = j-d
            y = j+d
            if x < 0:
                B[0] += 1
            else:
                B[x] += 1
            if N-1 < y:
                B[N] -= 1
            else:
                B[y+1] -= 1
        A = list( accumulate(B))
        check = True
        for j in range(N):
            if A[j] < N:
                check = False
        if check:
            break
    print(" ".join( map(str, A[:-1])))
            
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
Q = 998244353
def main():
    N, S = map( int, input().split())
    A = list( map( int, input().split()))
    invtwo = pow(2, Q-2, Q)
    # Invtwo = [1]
    # now = 1
    dp = [pow(2, N, Q)]+[0]*S
    for i in range(N):
        a = A[i]
        for i in range(S, a-1,-1):
            # print(i, a, i-a, dp[i-a])
            if dp[i-a] > 0:
                dp[i] += dp[i-a]*invtwo%Q
                dp[i] %= Q
        # print(dp)
    print(dp[S])
                
if __name__ == '__main__':
    main()


Fixed submission:
Q = 998244353
def main():
    N, S = map( int, input().split())
    A = list( map( int, input().split()))
    invtwo = pow(2, Q-2, Q)
    # Invtwo = [1]
    # now = 1
    dp = [pow(2, N, Q)]+[0]*S
    for i in range(N):
        a = A[i]
        for i in range(S, a-1,-1):
            # print(i, a, i-a, dp[i-a])
            if dp[i-a] > 0:
                dp[i] += dp[i-a]*invtwo%Q
                dp[i] %= Q
        # print(dp)
    print(dp[S])
                
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input())][::-1]
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += N-i
        print(ans)
        return
    L = [0]*P
    L[0] = 1
    t = 0
    s = 1
    for i in range(N):
        t = (S[i]*s+t)%P
        L[t] += 1
        s = s*10%P
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input())][::-1]
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += N-i
        print(ans)
        return
    L = [0]*P
    L[0] = 1
    t = 0
    for i in range(N):
        t = (S[i]*pow(10,i,P)+t)%P
        L[t] += 1
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#import sys
#input = sys.stdin.readline
def main():
    S = [ int(x) for x in input()]
    ans = 0
    N = len(S)
    l = 0
    r = 1
    d = dict()
    d[0] = 0
    d[1] = 1
    d[2] = 2
    d[3] = 3
    d[4] = 4
    d[5] = 5
    d[6] = 4
    d[7] = 3
    d[8] = 2
    d[9] = 1
    for i in range(N):
        if S[i] >= 5 and i < N-1:
            continue
        for s in range(l,i+1):
            if s == l and S[s] == 9:
                ans += 2
                continue
            ans += d[s]
        l = i
    print(ans)
            
if __name__ == '__main__':
    main()


Fixed submission:
def main():
    S = list( map( int, list( input())))
    N = len(S)
    dp = [[0,0] for _ in range(N+1)]
    dp[0][1] = 2
    for i in range(N):
        s = S[i]
        dp[i+1][0] = min(dp[i][0] + s, dp[i][1]+s)
        dp[i+1][1] = min(dp[i][0] + 11-s, dp[i][1]+9-s)
        # dp[i+1][2] = min(dp[i][1], dp[i][2])+9-s
        # 11-sは、追加で支払うものと、お釣り
        # 9-sは、追加はすでに支払われていて、繰り下がりが起こっている
    print( min(dp[N][0], dp[N][1]))
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    H, N = map( int, input().split())
    AB = [ list( map( int, input().split())) for _ in range(N)]
    dp = [10**9]*H + [0]*(10**4+1)
    T = H+10**4
    for a, b in AB:
        for i in range(T,a-1,-1):
            if dp[i-a] > dp[i]+b:
                dp[i-a] = dp[i]+b
    print(dp[0])
if __name__ == '__main__':
    main()


Fixed submission:
import sys
input = sys.stdin.readline
def main():
    H, N = map( int, input().split())
    AB = [ list( map( int, input().split())) for _ in range(N)]
    dp = [10**9]*H + [0]*(10**4+1)
    T = H+10**4
    for a, b in AB:
        for i in range(T,a-1,-1):
            if dp[i-a] > dp[i]+b:
                dp[i-a] = dp[i]+b
    print(dp[0])
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return(a)

def lcm(a, b):
    return a*b//gcd(a,b)
#import sys
#input = sys.stdin.readline
def main():
    N, M = map( int, input().split())
    A = list( map( int, input().split()))
    B = [a for a in A]
    T = 1
    L = 1
    C = [0]*N
    for i in range(30):
        if B[i]%2 == 0:
            B[i] //= 2
            C[i] += 1
    p = C[0]
    for i in range(N-1):
        if p != C[i+1]:
            print(0)
            return
    q = pow(2,p)
    t = 1
    for i in range(N):
        t = lcm(1,t)
    m = t*q
    if m > M:
        print(0)
        return
    print((M-m)//(q*t)+1)

if __name__ == '__main__':
    main()

Fixed submission:
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return(a)

def lcm(a, b):
    return a*b//gcd(a,b)
#import sys
#input = sys.stdin.readline
def main():
    N, M = map( int, input().split())
    A = list( map( int, input().split()))
    B = [a for a in A]
    T = 1
    L = 1
    C = [0]*N
    for i in range(N):
        for _ in range(30):
            if B[i]%2 == 0:
                B[i] //= 2
                C[i] += 1
            else:
                break
    p = C[0]
    for i in range(N-1):
        if p != C[i+1]:
            print(0)
            return
    q = pow(2,p)
    t = 1
    for i in range(N):
        t = lcm(t,A[i]//2)
    if t > M:
        print(0)
        return

    print((M-t)//(t*2) + 1)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return(a)

def lcm(a, b):
    return a*b//gcd(a,b)
#import sys
#input = sys.stdin.readline
def main():
    N, M = map( int, input().split())
    A = list( map( int, input().split()))
    B = [a for a in A]
    T = 1
    L = 1
    C = [0]*N
    for i in range(N):
        for _ in range(30):
            if B[i]%2 == 0:
                B[i] //= 2
                C[i] += 1
            else:
                break
    p = C[0]
    for i in range(N-1):
        if p != C[i+1]:
            print(0)
            return
    q = pow(2,p)
    t = 1
    for i in range(N):
        t = lcm(t,A[i]//2)
    if t > M:
        print(0)
        return

    print((M-t)//t + 1)

if __name__ == '__main__':
    main()



Fixed submission:
def main():
    N = int( input())
    Q = 10**9+7
    C = list( map( int, input().split()))
    C.sort()
    ans = 1
    if N == 1:
        print(C[0]*2%Q)
        return
    for i in range(N-1):
        ans += pow(2,i,Q)*(((N-1)-i)*pow(2,N-2-i,Q) + pow(2, N-1-i, Q))*C[i]%Q
        ans %= Q
    ans += pow(2, N-1, Q)*C[N-1]%Q
    ans -= 1
    print(ans*pow(2,N,Q)%Q)
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return(a)

def lcm(a, b):
    return a*b//gcd(a,b)
#import sys
#input = sys.stdin.readline
def main():
    N, M = map( int, input().split())
    A = list( map( int, input().split()))
    B = [a for a in A]
    T = 1
    L = 1
    C = [0]*N
    for i in range(N):
        for _ in range(30):
            if B[i]%2 == 0:
                B[i] //= 2
                C[i] += 1
            else:
                break
    p = C[0]
    for i in range(N-1):
        if p != C[i+1]:
            print(0)
            return
    q = pow(2,p)
    t = 1
    for i in range(N):
        t = lcm(t,A[i]//2)
    if t > M:
        print(0)
        return

    print((M-t)//t + 1)

if __name__ == '__main__':
    main()



Fixed submission:
def main():
    N = int( input())
    Q = 10**9+7
    C = list( map( int, input().split()))
    C.sort()
    ans = 1
    if N == 1:
        print(C[0]*2%Q)
        return
    for i in range(N-1):
        ans += pow(2,i,Q)*(((N-1)-i)*pow(2,N-2-i,Q) + pow(2, N-1-i, Q))*C[i]%Q
        ans %= Q
    ans += pow(2, N-1, Q)*C[N-1]%Q
    ans -= 1
    print(ans*pow(2,N,Q)%Q)
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
Q = 10**9 + 7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    T = [[0]*60 for _ in range(N)]
    for i in range(N):
        a = A[i]
        for j in range(60):
            T[i][j] = a%2
            a //= 2
    ans = 0
    for i in range(60):
        plus = sum( [1 for j in range(N) if T[j][i] == 1])
        minus = N - plus
        ans = (ans + plus*minus%Q*pow(2,i,Q))%Q
    print(ans)
        
if __name__ == '__main__':
    main()


Fixed submission:
#import sys
#input = sys.stdin.readline
Q = 10**9 + 7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    T = [[0]*60 for _ in range(N)]
    P = [0]*60
    for i in range(N):
        a = A[i]
        for j in range(60):
            T[i][j] = a%2
            P[j] += a%2
            a //= 2
    ans = 0
    for i in range(60):
        plus = P[i]
        minus = N - plus
        ans = (ans + plus*minus%Q*pow(2,i,Q))%Q
    print(ans)
        
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#import sys
#input = sys.stdin.readline
Q = 10**9 + 7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    T = [[0]*60 for _ in range(N)]
    for i in range(N):
        a = A[i]
        for j in range(60):
            T[i][j] = a%2
            a //= 2
    ans = 0
    for i in range(60):
        plus = sum( [1 for j in range(N) if T[j][i] == 1])
        minus = N - plus
        ans = (ans + plus*minus%Q*pow(2,i,Q))%Q
    print(ans)
        
if __name__ == '__main__':
    main()


Fixed submission:
#import sys
#input = sys.stdin.readline
Q = 10**9 + 7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    T = [[0]*60 for _ in range(N)]
    P = [0]*60
    for i in range(N):
        a = A[i]
        for j in range(60):
            T[i][j] = a%2
            P[j] += a%2
            a //= 2
    ans = 0
    for i in range(60):
        plus = P[i]
        minus = N - plus
        ans = (ans + plus*minus%Q*pow(2,i,Q))%Q
    print(ans)
        
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#import sys
#input = sys.stdin.readline
def main():
    N = int( input())
    S = input()
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N-1):

        for j in range(i+1, N):
            if S[i] == S[j]:
                dp[i+1][j+1] = min(dp[i][j] + 1, j-i)
    print( max( [ max(dp[i]) for i in range(N+1)]))
if __name__ == '__main__':
    main()


Fixed submission:
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    S = input()
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N-1):
        for j in range(i+1, N):
            if S[i] == S[j]:
                dp[i+1][j+1] = min(dp[i][j] + 1, j-i)
    print( max( [ max(dp[i]) for i in range(N+1)]))
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#import sys
#input = sys.stdin.readline
import heapq
def main():
    N = int( input())
    A = list( map( int, input().split()))
    B = list( map( int, input().split()))
    C = [(-B[i],i) for i in range(N)]
    heapq.heapify(C)
    ans = 0
    check = 0
    while check < N:
        a,i = heapq.heappop(C)
        a *= -1

        if B[i] == A[i]:
            check += 1
            continue
        ans += 1
        a -= B[i-1] + B[(i+1)%N]
        B[i] = a
        if B[i] == A[i]:
            check += 1
        elif B[i] > A[i]:
            heapq.heappush(C, (-a, i))
        else:
            print(-1)
            return

    print(ans)
        
if __name__ == '__main__':
    main()


Fixed submission:
#import sys
#input = sys.stdin.readline
import heapq
def main():
    N = int( input())
    A = list( map( int, input().split()))
    B = list( map( int, input().split()))
    C = [(-B[i],i) for i in range(N)]
    heapq.heapify(C)
    ans = 0
    check = 0
    while check < N:
        a,i = heapq.heappop(C)
        a *= -1

        if B[i] == A[i]:
            check += 1
            continue
        cnt = (B[i] - A[i])//(B[i-1] + B[(i+1)%N])
        if cnt == 0:
            print(-1)
            return
        ans += cnt        
        a -= (B[i-1] + B[(i+1)%N])*cnt
        B[i] = a
        if B[i] == A[i]:
            check += 1
        elif B[i] > A[i]:
            heapq.heappush(C, (-a, i))
        else:
            print(-1)
            return

    print(ans)
        
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def main():
    Q = 10**9+7
    N, M = map( int, input().split())
    S = list( map( int, input().split()))
    T = list( map( int, input().split()))
    dp = [ [0]*(M+1) for _ in range(N+1)]
    memo = [ [0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1]+1)%Q
            else:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j])%Q
    print(dp[N][M]+1)
if __name__ == '__main__':
    main()


Fixed submission:
#import sys
#input = sys.stdin.readline
def main():
    X, A = map( int, input().split())
    if X < A:
        print(0)
    else:
        print(10)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    Q = 10**9+7
    N, M = map( int, input().split())
    S = list( map( int, input().split()))
    T = list( map( int, input().split()))
    dp = [ [0]*(M+1) for _ in range(N+1)]
    memo = [ [0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1]+1)%Q
            else:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j])%Q
    print(dp[N][M]+1)
if __name__ == '__main__':
    main()


Fixed submission:
#import sys
#input = sys.stdin.readline
def main():
    Q = 10**9+7
    N, M = map( int, input().split())
    S = list( map( int, input().split()))
    T = list( map( int, input().split()))
    dp = [ [0]*(M+1) for _ in range(N+1)]
    memo = [ [0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1]+1)%Q
            else:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j])%Q
    print(dp[N][M]+1)
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#import sys
#input = sys.stdin.readline
def main():
    Q = 10**9+7
    N, M = map( int, input().split())
    S = list( map( int, input().split()))
    T = list( map( int, input().split()))
    dp = [ [0]*(M+1) for _ in range(N+1)]
    memo = [ [0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1]+1)%Q
            else:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j])%Q
    print(dp[N][M]+1)
if __name__ == '__main__':
    main()


Fixed submission:
#import sys
#input = sys.stdin.readline
def main():
    Q = 10**9+7
    N, M = map( int, input().split())
    S = list( map( int, input().split()))
    T = list( map( int, input().split()))
    dp = [ [0]*(M+1) for _ in range(N+1)]
    memo = [ [0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1]+1)%Q
            else:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j])%Q
    print(dp[N][M]+1)
if __name__ == '__main__':
    main()