Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02598 (python)

Fixed submission:
import math
n,k=map(int,input().split())
log=list(map(int,input().split()))
a=0
b=max(log)
if b==1:
  print(1)
  exit()
c=(a+b)//2
while True:
  div=0
  for i in range(n):
    div+=math.ceil(log[i]/c)-1
  if div<=k:
    b=c
    c=(a+b)//2
  else:
    a=c
    c=(a+b)//2
    
  if c==a or c==b:
    break
print(b)

Buggy submission (verdict: Runtime Error):
import math
n,k=map(int,input().split())
log=list(map(int,input().split()))
a=0
b=max(log)
c=(a+b)//2
while True:
  div=0
  for i in range(n):
    div+=math.ceil(log[i]/c)-1
  if div<=k:
    b=c
    c=(a+b)//2
  else:
    a=c
    c=(a+b)//2
    
  if c==a or c==b:
    break
print(b)

Buggy submission (verdict: Runtime Error):
import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=1
b=max(a)
c=(a+b)//2
while True:
  div=0
  for i in range(n):
    div+=math.ceil(a[i]/c)-1
  if div<=k:
    b=c
    c=(a+b)//2
  else:
    a=c
    c=(a+b)//2
    
  if c==a or c==b:
    break
print(b)
Problem p02623 (python)

Fixed submission:
from itertools import accumulate
from bisect import bisect_left
 
n,m,k=map(int,input().split())
a=list(accumulate([0]+list(map(int,input().split()))))
b=list(accumulate([0]+list(map(int,input().split()))))
#print(b)
mx=0
for i in range(n+1):
  if a[i]>k:continue
  #print('a[i];'+str(a[i]))
  idx=min(bisect_left(b,k-a[i]),m)
  #print(idx)
  if b[idx]>k-a[i]:idx-=1
  if a[i]+b[idx]>k:continue
  mx=max(mx,i+idx)
print(mx)

Buggy submission (verdict: Runtime Error):
from itertools import accumulate
from bisect import bisect_left

n,m,k=map(int,input().split())
a=accumulate([0]+list(map(int,input().split())))
b=accumulate([0]+list(map(int,input().split())))
mx=0
for i in range(n+1):
  idx=bisect_left(max(k-a[i],0),b)
  mx=max(mx,i+idx)
print(mx)
Problem p02624 (python)

Fixed submission:
n=int(input())
ass=0
for j in range(1,n+1):
  ass+=int(n/j)*(int(n/j)+1)*j//2
  
print(ass)

Buggy submission (verdict: Runtime Error):
from math import factorial
from functools import lru_cache

n,v=map(int,input().split())
m=10**9+7
#r!(0>r>M)
lis=[0]
def permutation(n, x, mod=10**9+7):
    # nPx
    # 順列
    # ex) permutaion(5, 2) = 20
    tmp = 1
    for i in range(n, n-x, -1):
        tmp = (tmp * i) % mod
    return tmp


def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
 
@lru_cache(maxsize=1000)
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p))%p

acc=0
for j in range(n+1):
  s=comb(n,j,m)
  t=s*permutation(v,j,m)%m
  acc+=((-1)**j)*t*(permutation(v-j,n-j,m))**2%m
print(acc%m)

Buggy submission (verdict: Runtime Error):
import math
def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def seanum(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num
n=int(input())
print(sum([i*seanum(i) for i in range(1,n+1)])

Buggy submission (verdict: Runtime Error):
import sympy
n=int(input())
a=0
for i in range(1,n+1):
  
  a+=sympy.divisor_count(i)
print(a)
Problem p02625 (python)

Fixed submission:
from collections import deque
#from functools import lru_cache

def permutation(n, x, mod=10**9+7):
    # nPx
    # 順列
    # ex) permutaion(5, 2) = 20
    tmp = 1
    for i in range(n, n-x, -1):
        tmp = (tmp * i) % mod
    return tmp

def power_func(a,n,p=10**9+7):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) %p
        if bi[i] == "1":
            res = (res*a) %p
    return res


n,v=map(int,input().split())
m=10**9+7
perm1=deque([1])
perm2=deque([permutation(v,n)])
comb=deque([1])
ones=deque([1])
acc=((comb[-1]*perm1[-1]%m)*perm2[-1]**2)%m
for k in range(n):
  #nCk+1=nCk*(n-k/k+1)
  comb.append((comb.pop()*(n-k)*power_func(k+1,m-2))%m)
  #vPk+1=vPk*(v-k)
  perm1.append((perm1.pop()*(v-k))%m)
  #v-(k+1)Pn-(k+1)=v-kPn-k/(v-k)
  perm2.append((perm2.pop()*power_func(v-k,m-2))%m)
  #(-1)^k+1=(-1)^k*(-1)
  ones.append(ones.pop()*(-1))
  acc+=ones[-1]*((comb[-1]*perm1[-1]%m)*perm2[-1]**2)%m
print(acc%m)

Buggy submission (verdict: Runtime Error):
n,m=map(int,input().split())
m=10**9+7
#r!(0>r>M)
lis=[0]
for q in range(1,n+1):
  lis.append(lis[-1]*q%m)
from functools import lru_cache
@lru_cache(maxsize=1000)
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

@lru_cache(maxsize=1000)
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
acc=0
for j in range(n+1):
  s=comb(n,j,m)
  t=s*(factorial(m)//factorial(j))%m
  acc+=((-1)**j)*t*(factorial(m-j)//factorial(n-j))**2%m
print(acc%m)
Problem p02659 (python)

Fixed submission:
# fp = open('integer.txt')
A,B = input().split()
B = B.split('.')
B = B[0]+B[1]
B = int(B)
X = str(int(A)*B)
if len(X)<=2:
    print(0)
else:
    print(X[0:len(X)-2])

Buggy submission (verdict: Runtime Error):
a,b=input().split()

a=list(a)
b=list(b)
a0=int(''.join(a))
a1=int(''.join(a[:-1]))
a2=int(''.join(a[:-2]))
b0=int(b[0])
b1=int(b[2])
b2=int(b[3])
ss=a0*b0+a1*b1+a2*b2
print(ss)
Problem p02661 (python)

Fixed submission:
n=int(input())
alis=[]
blis=[]
for i in range(n):
  a,b=map(int,input().split())
  alis.append(a)
  blis.append(b)
  
  
alis=sorted(alis)
blis=sorted(blis)
if n%2!=0:
  print(blis[int((n-1)/2)]-alis[int((n-1)/2)]+1)
else:
  bb=(blis[int(n/2)-1]+blis[int(n/2)])
  aa=(alis[int(n/2)-1]+alis[int(n/2)])
  print(bb-aa+1)

Buggy submission (verdict: Runtime Error):
n=int(input())
alis=[]
blis=[]
for i in range(n):
  a,b=map(int,input().split())
  alis.ppend(a)
  blis.append(b)
  
  
alis=sorted(alis)
blis=sorted(blis)
if n%2!=0:
  print(blis[int((n-1)/2)]-alis[int((n-1)/2)]+1)
else:
  bb=(blis[int(n/2)-1]+blis[int(n/2)])
  aa=(alis[int(n/2)-1]+alis[int(n/2)])
  print(bb-aa+1)

Buggy submission (verdict: Runtime Error):
n=int(input())
alis=[]
blis=[]
for i in range(n):
  a,b=map(int,input().split())
  alis.ppend(a)
  blis.append(b)
  
  
alis=sorted(alis)
blis=sorted(blis)
if n%2!=0:
  print(blis[int((n-1)/2)]-alis[int((n-1)/2)+1]
else:
  bb=(blis[int(n/2)-1]+blis[int(n/2)])
  aa=(alis[int(n/2)-1]+alis[int(n/2)])
  print(bb-aa+1)
Problem p02676 (python)

Fixed submission:
k=int(input())
s=input()
n=len(s)
if n<=k:
  print(s)
else:
  print(s[:k]+'...')

Buggy submission (verdict: Runtime Error):
k=int(input())
s=input()
n=len(s)
if s<=k:
  print(s)
else:
  print(s[:k]+'...')
Problem p02682 (python)

Fixed submission:
a,b,c,k=map(int,input().split())
if a>=k:
  print(k)
else:
  if a+b>=k:
    print(a)
  else:
    print(a-(k-a-b))

Buggy submission (verdict: Runtime Error):
a,b,c,k=map(int,input().split())
if a>=k:
  print(a)
  break
else:
  if a+b>=k:
    print(a)
    break
  else:
    print(a-(k-a-b))
    break
Problem p02688 (python)

Fixed submission:
import numpy as np
N, K = map(int, input().split())
N_lis=np.zeros(N)
for i in range(K):
    d=int(input())
    sweet=np.array(list(map(int, input().split())))
    #print(sweet)
    sweet-=1
    for j in sweet:
        N_lis[j]+=1
#print(N_lis)
no_sweet=N_lis==0
#print(no_sweet)
print(no_sweet.sum())

Buggy submission (verdict: Runtime Error):
import numpy as np
N, K = map(int, input().split())
N_lis=np.zeros(N)
for i in range(K):
    d=int(input())
    sweet=np.array(list(map(int, input().split())))
    #print(sweet)
    sweet-=1
    for j in sweet:
        N_lis[j]+=1
print(N_lis)
no_sweet=N_lis==0
print(no_sweet)
print(no_sweet.sum()))

Buggy submission (verdict: Runtime Error):
import numpy as np
N, K = map(int, input().split())
N_lis=np.zeros(N)
for i in range(K):
  d=int(input())
  sweet=np.array(map(int, input().split()))
  sweet-=1
  for j in sweet:
    N_lis[j]+=1
 
no_sweet=N_lis[N_lis==0]
print(no_sweet.sum())

Buggy submission (verdict: Runtime Error):
import numpy as np
N, K = map(int, input().split())
N_lis=np.zeros(N)
for i in range(K):
  d=int(input())
  sweet=np.arrray(map(int, input().split()))
  sweet-=1
  for j in sweet:
    N_lis[j]+=1

no_sweet=N_lis[N_lis==0]
print(no_sweet.sum())
Problem p02689 (python)

Fixed submission:
n,m=map(int,input().split())
h=list(map(int,input().split()))
dic={i:set() for i in range(n)}
for j in range(m):
  a,b=map(lambda x:int(x)-1,input().split())
  dic[a].add(b)
  dic[b].add(a)
co=0
for i in range(n):
  if all([h[i]>h[way] for way in dic[i]]):co+=1
print(co)

Buggy submission (verdict: Runtime Error):
H=[int(x) for x in input().split()]
way=[]
for i in range(M):
    way.append([int(x) for x in input().split()])
 
dic={}
for i in range(N):
    dic[i]=set()
 
for h in way:
    dic[h[0]-1].add(h[1]-1)
    dic[h[1]-1].add(h[0]-1)
    
 
print(sum(all([H[i]>H[hs] for hs in dic[i]])for i in range(N)))

Buggy submission (verdict: Runtime Error):
import numpy as np
N,M =map(int,input().split())
h_lis=np.array(list(map(int,input().split())))
way_lis=[list(map(int,input().split())) for _ in range(M)]

tes=0
for i in range(N):
    nears=[]
    for way in way_lis:
        if i+1 in way:
            near.extend(way)
    for j,ne in enumerate(nears):
        if j==0:
            h=max(h_lis[ne[0]-1],h_lis[ne[1]-1])
            z=h
        else:
            k=z
            h=max(h_lis[ne[0]-1],h_lis[ne[1]-1])
            z=max(k,h)
    if z==h_lis[i]:
        tes+=1
print(tes)
Problem p02695 (python)

Fixed submission:
from itertools import combinations_with_replacement
n,m,q=map(int,input().split())
aa=[]
bb=[]
cc=[]
dd=[]
for i in range(q):
  a,b,c,d=map(int,input().split())
  aa.append(a-1)
  bb.append(b-1)
  cc.append(c)
  dd.append(d)
sumd=[]
#print(list(combinations(range(1,m+1),n)))
for Alis in combinations_with_replacement(range(1,m+1),n):
  
  di=0
  
  for i in range(q):
    if cc[i]==(Alis[bb[i]]-Alis[aa[i]]):
      di+=dd[i]
      
  sumd.append(di)
print(max(sumd))

Buggy submission (verdict: Runtime Error):
from itertools import combinations
n,m,q=map(int,input().split())
aa=[]
bb=[]
cc=[]
dd=[]
for i in range(q):
  a,b,c,d=map(int,input().split())
  aa.append(a-1)
  bb.append(b-1)
  cc.append(c)
  dd.append(d)
sumd=[]
#print(list(combinations(range(1,m+1),n)))
for Alis in combinations(range(1,m+1),n):
  
  di=0
  
  for i in range(q):
    if cc[i]==(Alis[bb[i]]-Alis[aa[i]]):
      di+=dd[i]
      
  sumd.append(di)
print(max(sumd))

Buggy submission (verdict: Runtime Error):
for i in range(q):
  a,b,c,d=map(int,input().split())
  aa.append(a-1)
  bb.append(b-1)
  cc.append(c)
  dd.append(d)
sumd=[]
#print(list(combinations(range(1,m+1),n)))
for Alis in combinations(range(1,m+1),n):
  
  di=0
  
  for i in range(q):
    if cc[i]==(Alis[bb[i]]-Alis[aa[i]]):
      di+=dd[i]
      
  sumd.append(di)
print(max(sumd))
Problem p02701 (python)

Fixed submission:
N=int(input())
A_=set([input() for i in range(N)])
print(len(A_))

Buggy submission (verdict: Runtime Error):
N=int(input())
A_=set(list(map(int,input().split())))
print(len(A_))

Buggy submission (verdict: Runtime Error):
import pandas
N=int(input())
A_=list(map(int,input().split()))
ss=pd.Series(A_)
print(len(pd.unique(ss))
Problem p02781 (python)

Fixed submission:
import sys
import math
sys.setrecursionlimit(10 ** 7)

# 桁DP
# 再帰

N = input()
K = int(input())
lenN = len(N)


# 組み合わせの数
def comb(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n-k))


# i桁目から
# 残りk個 Non-Zero
# Nよりもsmallerか？
# というときの組み合わせの数
def CntAlmostZero(i, k, smaller):
    # N桁まで取り出した時
    if i == lenN:
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    # Nよりも小さい時
    if smaller:
        # 残りの桁でK個使える時
        if (lenN - i) >= k:
            return comb(lenN - i, k) * (9 ** k)
        # 無理なら 0
        else:
            return 0
    # 前がNと同じ桁の時(初期は0なので必ずこっち)
    else:
        # 見てる桁が0の時
        if N[i] == '0':
            return CntAlmostZero(i + 1, k, False)
        # 見てる桁が0以外の時
        else:
            # 0だったら
            zero = CntAlmostZero(i+1, k, True)
            # 同じだったら
            same = CntAlmostZero(i+1, k-1, False)
            # その間だったら
            aida = CntAlmostZero(i+1, k-1, True) * (int(N[i]) - 1)

            return zero + same + aida

    return 1


ans = CntAlmostZero(0, K, False)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import math
sys.setrecursionlimit(10 ** 7)

# 桁DP
# 再帰

N = input()
K = int(input())
lenN = len(N)


# 組み合わせの数
def comb(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n-k))


# i桁目から
# 残りk個 Non-Zero
# Nよりもsmallerか？
# というときの組み合わせの数
def CntAlmostZero(i, k, smaller):
    # N桁まで取り出した時
    if i == lenN:
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    # Nよりも小さい時
    if smaller:
        return comb(lenN - i, k) * (9 ** k)
    # 前がNと同じ桁の時(初期は0なので必ずこっち)
    else:
        # 見てる桁が0の時
        if N[i] == '0':
            return CntAlmostZero(i + 1, k, False)
        # 見てる桁が0以外の時
        else:
            # 0だったら
            zero = CntAlmostZero(i+1, k, True)
            # 同じだったら
            same = CntAlmostZero(i+1, k-1, False)
            # その間だったら
            aida = CntAlmostZero(i + 1, k - 1, True) * (int(N[i]) - 1)

            return zero + same + aida

    return 1


ans = CntAlmostZero(0, K, False)
print(ans)
Problem p02873 (python)

Fixed submission:
S = list(input())
N = len(S) + 1

from_left = [0] * N
from_right = [0] * N

for i in range(N-1):
  s = S[i]
  if s == '<':
    from_left[i+1] = from_left[i] + 1

for i in range(N-2,-1,-1):
  s = S[i]
  if s == '>':
    from_right[i] = from_right[i+1] + 1
    
ans = 0
for i in range(N):
  ans += max(from_left[i],from_right[i])
  
print(ans)

Buggy submission (verdict: Runtime Error):
S = list(input())
N = len(S) + 1

mn = 0
ans = 0
for s in S:
  if s == '<':
    a += 1
  elif s == '>':
    a -= 1
    mn = min(mn,a)    
  
  ans += a
  
ans -= mn * N
print(ans)

Buggy submission (verdict: Runtime Error):
S = list(input())

mn = 0
ans = 0
for s in S:
  if s == '<':
    a += 1
  elif s == '>':
    a -= 1
    mn = min(mn,a)    
  
  ans += a
  
ans -= mn * (len(S) + 1)
print(ans)

Buggy submission (verdict: Runtime Error):
S = list(input())

mn = 0
ans = 0
for s in S:
  if s == '<':
    a += 1
  elif s == '>':
    a -= 1
    mn = min(mn,a)    
  
  ans += a
  
plus = -mn
ans += plus * (len(S) + 1)
print(ans)
Problem p02897 (python)

Fixed submission:
N = int(input())

if N == 1:
  print(1)
elif N % 2 == 0:
  print(0.5)
else:
  print(-(-N//2) / N)

Buggy submission (verdict: Runtime Error):
N = int(input())

if N == 1:
  print(1)
elif N % 2 == 0:
  print(0.5)
else:
  print((N - (N//2) / N)
Problem p02990 (python)

Fixed submission:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MOD = 10 ** 9 + 7


# 階乗、Combinationコンビネーション(numpyを使う)
def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


U = 10**4
fact, fact_inv = make_fact(U, MOD)
fact, fact_inv = fact.tolist(), fact_inv.tolist()


def mod_comb_k(n, k, mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod


ans = []
red = N - K

# i回操作する方法
for i in range(1, K + 1):
    #print("i=", i)
    res = 1

    # i分割するためには、i-1個ボールが必要
    if red < (i - 1):
        ans.append(str(0))
        continue

    # i分割する
    # i-1箇所に置く
    pat_split = 1
    pat_split *= mod_comb_k(K - 1, i - 1, MOD)

    #print("pat_split", pat_split)

    # 残りの玉を置く
    pat_rest = i - 1 + 2
    bal_rest = N - (i - 1) - K
    res *= mod_comb_k(pat_rest + bal_rest - 1, bal_rest, MOD)
    #print("res", res)
    res *= pat_split
    res %= MOD

    ans.append(str(res))

print("\n".join(ans))

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MOD = 10 ** 9 + 7


# 階乗、Combinationコンビネーション(numpyを使う)
def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


U = 10**3
fact, fact_inv = make_fact(U, MOD)
fact, fact_inv = fact.tolist(), fact_inv.tolist()


def mod_comb_k(n, k, mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod


ans = []

# i回操作する方法
for i in range(1, K + 1):
    #print("i=", i)
    res = 1

    # i分割する
    # i-1箇所に置く
    pat_split = 1
    pat_split *= mod_comb_k(K - 1, i - 1, MOD)

    #print("pat_split", pat_split)

    # 残りの玉を置く
    pat_rest = i - 1 + 2
    bal_rest = N - (i - 1) - K
    res *= mod_comb_k(pat_rest + bal_rest - 1, bal_rest, MOD)
    #print("res", res)
    res *= pat_split
    res %= MOD

    ans.append(str(res))

print("\n".join(ans))
Problem p03003 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

MOD = 10 ** 9 + 7

dp = [[0] * (M+1) for _ in range(N+1)]
dp_cum = [[0] * (M+1) for _ in range(N+1)]

for x in range(N):
    for y in range(M):
        if S[x] == T[y]:
            dp[x + 1][y + 1] += dp_cum[x][y] + 1
            dp[x + 1][y + 1] %= MOD

        dp_cum[x + 1][y + 1] = (dp_cum[x+1][y] % MOD) \
            + (dp_cum[x][y + 1] % MOD) \
            - (dp_cum[x][y] % MOD) \
            + (dp[x + 1][y + 1] % MOD)

        dp_cum[x + 1][y + 1] %= MOD

        #print("---x,y", x, y, "----")
        #print("dp:", dp)
        #print("dp_cum", dp_cum)


ans = dp_cum[N][M] + 1
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import bisect
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MOD = 10 ** 9 + 7

if N < M:
    N, M = M, N
    S, T = T, S

idxs = {}
for n in range(10):
    arr = [i for i, x in enumerate(S) if x == n]
    idxs[n] = arr


@lru_cache(maxsize=None)
def solve(i, j):
    arr1 = S[i:]
    arr2 = T[j:]

    if len(arr1) == 0 or len(arr2) == 0:
        return 1

    ans = 0
    t = arr2[0]

    t_idxs = idxs[t]
    l = bisect.bisect_left(t_idxs, i)
    # print(idxs)

    for idx in t_idxs[l:]:
        ans += solve(idx + 1, j + 1)
        ans %= MOD

    ans += solve(i, j + 1)
    ans %= MOD

    #print("i,j,ans", i, j, ans)

    return ans


r = solve(0, 0)

print(r)

Buggy submission (verdict: Runtime Error):
import sys
import bisect
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MOD = 10 ** 9 + 7

if N < M:
    N, M = M, N
    S, T = T, S

idxs = {}
for n in range(10):
    arr = [i for i, x in enumerate(S) if x == n]
    idxs[n] = arr


@lru_cache(maxsize=None)
def solve(i, j):
    arr1 = S[i:]
    arr2 = T[j:]

    if len(arr1) == 0 or len(arr2) == 0:
        return 1

    ans = 0
    t = arr2[0]

    t_idxs = idxs[t]
    l = bisect.bisect_left(t_idxs, i)
    # print(idxs)

    for idx in t_idxs[l:]:
        ans += solve(idx + 1, j + 1)
        ans %= MOD

    ans += solve(i, j + 1)
    ans %= MOD

    #print("i,j,ans", i, j, ans)

    return ans


r = solve(0, 0)

print(r)
Problem p03013 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [True] * (N+10)
MOD = 10 ** 9 + 7
for _ in range(M):
  x = int(readline())
  A[x] = False


DP = [0] * (N+10)
DP[0] = 1

for i in range(N):
  if not A[i]:
    continue
  
  if A[i+1]:
    DP[i+1] += DP[i]
    DP[i+1] %= MOD
  if A[i+2]:
    DP[i+2] += DP[i]
    DP[i+2] %= MOD
       
print(DP[N]%MOD)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [True] * (N+10)
MOD = 10 ** 9 + 7
for _ in range(M):
  x = int(readline())
  A[x] = False


DP = [0] * (N+10)
DP[0] = 1

for i in range(N):
  if not A[i]:
    continue
  
  if A[i+1]:
    DP[i+1] += DP[i]
    DP[i+1] %= MOD
  if A[i+2]:
    DP[i+2] += DP[i]
    DP[i+2]: %= MOD
       
print(DP[N]%MOD)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [True] * (N+10)
MOD = 10 ** 9 + 7
for _ in range(M):
  x = int(readline())
  A[x] = False


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

for i in range(N):
  if not A[i]:
    continue
  
  if A[i+1]:
    DP[i+1] += DP[i]
    DP[i+1] %= MOD
  if A[i+2]:
    DP[i+2] += DP[i]
    DP[i+2]: %= MOD
       
print(DP[N]%MOD)