Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
    return sys.stdin.readline()[:-1]
N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()
l=[None]*K
a=0
for i in range(K):
    t=0
    l[i]=T[i:N:K]
    for j in l[i]:
        if j=="r":
            if t!=1:
                a+=P
                t=1
            else:
                t=0
        if j=="s":
            if t!=2:
                a+=R
                t=2
            else:
                t=0
        if j=="p":
            if t!=3:
                a+=S
                t=3
            else:
                t=0
print(a)

Fixed submission:
N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()
a=0
for i in range(K):
    t=0
    l=T[i:N:K]
    for j in l:
        if j=="r":
            if t!=1:
                a+=P
                t=1
            else:
                t=0
        if j=="s":
            if t!=2:
                a+=R
                t=2
            else:
                t=0
        if j=="p":
            if t!=3:
                a+=S
                t=3
            else:
                t=0
print(a)
Buggy python submission (verdict: Runtime Error):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,A,B=map(int,input().split())
if (B-A)%2==0:5 2 
    print((B-A)//2)
else:
    print(min(B-1,N-A))

Fixed submission:
N,A,B=map(int,input().split())
if (B-A)%2==0:
    print((B-A)//2)
else:
    print(min((B+A-1)//2,((2*N-B+1-A)//2)))
Buggy python submission (verdict: Runtime Error):
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
A=list(map(int,input().split()))
l=[0]*59
for i in A:
    s=str(bin(i))[2:]
    for j in range(len(s)):
        if s[-j-1]=="1":
            l[j]+=1
a=0
for i in range(59):
    a=(a+2**i*l[i]*(N-l[i]))%(10**9+7)
print(a)

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
A=list(map(int,input().split()))
l=[0]*60
for i in A:
    s=str(bin(i))[2:]
    for j in range(len(s)):
        if s[-j-1]=="1":
            l[j]+=1
a=0
for i in range(60):
    a=(a+2**i*l[i]*(N-l[i]))%(10**9+7)
print(a)
Buggy python submission (verdict: Runtime Error):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
S = [list(map(int, input().split()))+[i] for i in range(N-1)]
A=[None]*(N-1)
l=[[] for i in range(N+1)]
t=[0]*N
t[0]=1
for i in S:
    l[i[0]].append((i[1],i[2]))
    l[i[1]].append((i[0],i[2]))
def haba(o,c):
    p=1
    for i in l[o]:
        if t[i[0]-1]==0:
            if c==p:
                p+=1
            A[i[1]]=p
            t[i[0]-1]=1
            haba(i[0],p)
            p+=1
haba(1,0)
print(max(A))
print(*A,sep="\n")

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N=int(input())
S = [list(map(int, input().split()))+[i] for i in range(N-1)]
A=[None]*(N-1)
l=[[] for i in range(N+1)]
t=[0]*N
t[0]=1
for i in S:
    l[i[0]].append((i[1],i[2]))
    l[i[1]].append((i[0],i[2]))
def haba(o,c):
    p=1
    for i in l[o]:
        if t[i[0]-1]==0:
            if c==p:
                p+=1
            A[i[1]]=p
            t[i[0]-1]=1
            haba(i[0],p)
            p+=1
haba(1,0)
print(max(A))
print(*A,sep="\n")
Buggy python submission (verdict: Runtime Error):
N=int(input())
L=tuple(map(int,input().split()))
l=[0]*1001
g=[0]*1001
for i in L:
    l[i]+=1
for i in range(1,1001):
    g[i]=g[i-1]+l[i]
a=0
for i in range(1,999):
    for j in range(i+1,1000):
        a+=l[i]*l[j]*(g[min(i+j-1,1000)]-g[j])
for i in range(1,1001):
    if l[i]>1:
        t=l[i]*(l[i]-1)//2
        for j in range(1,i):
            a+=t*l[j]
        if l[i]>2:
            a+=t*(l[i]-2)//3
        for j in range(i+1,min(1001,l[i*2])):
            a+=t*l[j]
print(a)

Fixed submission:
N=input()
L=tuple(map(int,input().split()))
l=[0]*1001
g=[0]*1001
for i in L:
    l[i]+=1
for i in range(1,1001):
    g[i]=g[i-1]+l[i]
a=0
for i in range(1,999):
    for j in range(i+1,1000):
        a+=l[i]*l[j]*(g[min(i+j-1,1000)]-g[j])
for i in range(1,1001):
    if l[i]>1:
        t=l[i]*(l[i]-1)//2
        for j in range(1,i):
            a+=t*l[j]
        if l[i]>2:
            a+=t*(l[i]-2)//3
        for j in range(i+1,min(1001,i*2)):
            a+=t*l[j]
print(a)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
L=2**N
l=[float("inf")]*L
l[0]=0
r=(1,2,4,8,16,32,64,128,256,512,1024,2048)
for i in range(M):
    s=0
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    for j in c:
        s+=r[j-1]
    for j in range(L):
        l[j|s]=min(l[j|s],l[j]+a)
if l[-1]==float("inf"):
    print(-1)
else:
    print(l[-1])

Fixed submission:
from itertools import product
N,M=map(int,input().split())
l=list(product((0,1),repeat=N))
L=len(l)
for i in range(2**N):
    l[i]=[l[i],1300000]
r=(2048,1024,512,256,128,64,32,16,8,4,2,1)
l[0][1]=0
for i in range(M):
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    t=[0]*N
    for j in c:
        t[-j]=1
    for j in range(L):
        s=0
        for k in range(N):
            if l[j][0][-k-1] or t[-k-1]:
                s+=r[-k-1]
        l[s][1]=min(l[j][1]+a,l[s][1])
if l[-1][1]==1300000:
    print(-1)
else:
    print(l[-1][1])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
N,M=map(int,input().split())
l=list(product((0,1),repeat=N))
L=len(l)
for i in range(2**N):
    l[i]=[l[i],1300000]
r=(2048,1024,512,256,128,64,32,16,8,4,2,1)
l[0][1]=0
for i in range(M):
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    t=[0]*N
    for j in c:
        t[-j]=1
    for j in range(L):
        s=0
        for k in range(N):
            if l[j][0][-k-1] or t[-k-1]:
                s+=r[-k-1]
        l[s][1]=min(l[j][1]+a,l[s][1])
if l[-1][1]==1300000:
    print(-1)
else:
    print(l[-1][1])

Fixed submission:
from itertools import product
N,M=map(int,input().split())
l=list(product((0,1),repeat=N))
L=len(l)
for i in range(2**N):
    l[i]=[l[i],1300000]
r=(2048,1024,512,256,128,64,32,16,8,4,2,1)
l[0][1]=0
for i in range(M):
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    t=[0]*N
    for j in c:
        t[-j]=1
    for j in range(L):
        s=0
        for k in range(N):
            if l[j][0][-k-1] or t[-k-1]:
                s+=r[-k-1]
        l[s][1]=min(l[j][1]+a,l[s][1])
if l[-1][1]==1300000:
    print(-1)
else:
    print(l[-1][1])
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import insort_left
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for _ in range(M):
    m=A.pop(-1)
    insort_left(A,m//2)
print(sum(A))

Fixed submission:
import heapq
N,M=map(int,input().split())
A=tuple(map(int,input().split()))
l=[(-i,i) for i in A]
heapq.heapify(l)
for _ in range(M):
    m=heapq.heappop(l)
    heapq.heappush(l,(-(m[1]//2),m[1]//2))
a=0
for i in l:
    a+=i[1]
print(a)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import insort_left
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for _ in range(M):
    m=A.pop(-1)
    insort_left(A,m//2)
print(sum(A))

Fixed submission:
import heapq
N,M=map(int,input().split())
A=tuple(map(int,input().split()))
l=[(-i,i) for i in A]
heapq.heapify(l)
for _ in range(M):
    m=heapq.heappop(l)
    heapq.heappush(l,(-(m[1]//2),m[1]//2))
a=0
for i in l:
    a+=i[1]
print(a)
Buggy python submission (verdict: Runtime Error):
S=input()
T=input()
a=0
for i in range(3):
    if S[i]==T[i]:
        a+=1
print(a)

Fixed submission:
A,B=map(int,input().split())
a=0
t=1
while t<B:
    t+=A-1
    a+=1
print(a)
Buggy python submission (verdict: Runtime Error):
N,Q=map(int,input().split())
l=[[1,0,0]]
for i in range(1,N):
    a,b=map(int,input().split())
    l.append([b,a,0])
l.sort()
for i in range(Q):
    p,x=map(int,input().split())
    l[p-1][2]+=x
t=[l[0][2]]
for i in range(1,N):
    t.append(t[l[i][1]-1]+l[i][2])
print(*t)

Fixed submission:
N=int(input())
v= list(map(int, input().split()))
v.sort()
t=(v[0]+v[1])/2
for i in range(2,N):
    t=(t+v[i])/2
print(t)
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
L=len(S)
s=[1]*L
l=[s]
def k(s):
    t=[0]*L
    for i in range(L):
        if S[i]=="R":
            t[i+1]+=s[i]
        else:
            t[i-1]+=s[i]
    return(t)
while 1:
    l.append(k(s))
    for i in range(len(l)-1):
        if l[-1]==l[i]:
            a=len(l)-1-i
            d=i
            break
    else:
        s=l[-1]
        continue
    break
A=l[(10**100-d)%a+d]
for i in A:
    print(i,end=" ")

Fixed submission:
S=input()
L=len(S)
l=[0]*L
b=0
while 1:
    t=1
    while 1:
        b+=1
        if S[b]=="R":
            t+=1
        else:
            break
    l[b]+=t//2
    l[b-1]+=t-t//2
    t=1
    while 1:
        if b==L-1:
            b+=1
            break
        b+=1
        if S[b]=="L":
            t+=1
        else:
            break
    l[b-t-1]+=t//2
    l[b-t]+=-(-t//2)
    if b==L:
        break
for i in l:
    print(i,end=" ")
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
a= list(map(int, input().split()))
a.sort()
b=[None]*N
b[0]=a[0]
A=0
for i in range(N-1,0,-1):
  b[1]=a[i]
  for j in range(2,N):
    b[j]=b[j-1]^b[j-2]
    if b[j] not in a:
      break
  else:
    b.sort()
    if a==b:
      A=1
      break
if A==1:
  print("Yes")
else:
  print("No")


Fixed submission:
N=int(input())
a=list(map(int,input().split()))
t=0
for i in a:
    t=t^i
print("No" if t else "Yes")

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
a= list(map(int, input().split()))
a.sort()
b=[None]*N
b[0]=a[0]
A=0
for i in range(1,N):
  b[1]=a[i]
  for j in range(2,N):
    b[j]=b[j-1]^b[j-2]
    if b[j] not in a:
      break
  else:
    b.sort()
    if a==b:
      A=1
      break
if A==1:
  print("Yes")
else:
  print("No")


Fixed submission:
N=int(input())
a=list(map(int,input().split()))
t=0
for i in a:
    t=t^i
print("No" if t else "Yes")

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
a= list(map(int, input().split()))
a.sort()
b=[None]*N
b[0]=a[0]
A=0
for i in range(1,N):
  b[1]=a[i]
  for j in range(2,N):
    b[j]=b[j-1]^b[j-2]
    if b[j] not in a:
      break
  else:
    b.sort()
    if a==b:
      A=1
      break
if A==1:
  print("Yes")
else:
  print("No")


Fixed submission:
N=int(input())
a=list(map(int,input().split()))
t=0
for i in a:
    t=t^i
print("No" if t else "Yes")

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
a= list(map(int, input().split()))
a.sort()
b=[None]*N
b[0]=a[0]
A=0
for i in range(1,N):
  b[1]=a[i]
  for j in range(2,N):
    b[j]=b[j-1]^b[j-2]
  b.sort()
  if a==b:
    A=1
    break
if A==1:
  print("Yes")
else:
  print("No")


Fixed submission:
N=int(input())
a=list(map(int,input().split()))
t=0
for i in a:
    t=t^i
print("No" if t else "Yes")
Buggy python submission (verdict: Runtime Error):
import numpy
N=int(input())
A=input().split()
for i in range(N):
    A[i]=2*int(A[i])
x=[None]*N
for i in range(N-1):
    x[i]=[0]*N
    x[i][i],x[i][i+1]=1,1
x[N-1]=[0]*N
x[N-1][0],x[N-1][N-1]=1,1
y=numpy.linalg.solve(x,A)
for i in range(N):
    print(int(y[i]),end=' ')


Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
A=list(map(int,input().split()))
y=0
for i in range(N-1):
    y=2*(A[i]-y//2)
l=[None]*N
l[0]=(2*A[-1]-y)//2
for i in range(1,N):
    l[i]=2*(A[i-1]-l[i-1]//2)
print(*l)

Buggy python submission (verdict: Runtime Error):
from numpy.linalg import solve
N=int(input())
A=input().split()
for i in range(N):
    A[i]=2*int(A[i])
x=[None]*N
for i in range(N-1):
    x[i]=[0]*N
    x[i][i],x[i][i+1]=1,1
x[N-1]=[0]*N
x[N-1][0],x[N-1][N-1]=1,1
y=solve(x,A)
for i in range(N):
    print(int(y[i]),end=' ')

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
A=list(map(int,input().split()))
y=0
for i in range(N-1):
    y=2*(A[i]-y//2)
l=[None]*N
l[0]=(2*A[-1]-y)//2
for i in range(1,N):
    l[i]=2*(A[i-1]-l[i-1]//2)
print(*l)

Buggy python submission (verdict: Time Limit Exceeded):
from numpy.linalg import solve
N=int(input())
A=input().split()
for i in range(N):
    A[i]=2*int(A[i])
x=[None]*N
for i in range(N-1):
    x[i]=[0]*N
    x[i][i],x[i][i+1]=1,1
x[N-1]=[0]*N
x[N-1][0],x[N-1][N-1]=1,1
y=solve(x,A)
for i in range(N):
    print(int(y[i]),end=' ')


Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
A=list(map(int,input().split()))
y=0
for i in range(N-1):
    y=2*(A[i]-y//2)
l=[None]*N
l[0]=(2*A[-1]-y)//2
for i in range(1,N):
    l[i]=2*(A[i-1]-l[i-1]//2)
print(*l)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
l1=[i for i in range(3) if B[i]>A[i]]
l2=[i for i in range(3) if B[i]<A[i]]
r=[B[i]-A[i] for i in range(3)]
def b(l):
    global N
    if len(l)==3:
        for i in range(N//A[0]+1):
            for j in range((N-i*A[0])//A[1]+1):
                k=(N-i*A[0]-j*A[1])//A[2]
                N=max(M,i*B[0]+j*B[1]+k*B[2]+(N-i-j-k))
    elif len(l)==2:
        for i in range(N//A[l[0]]+1):
            j=(N-i*A[l[0]])//A[l[1]]
            N=max(M,i*B[l[0]]+j*B[l[1]]+(N-i-j))
    elif len(l)==1:
        i=N//A[l[0]]
        N=i*B[l[0]]+N-i
def b2(l):
    global N
    if len(l)==3:
        for i in range(N//B[0]+1):
            for j in range((N-i*B[0])//B[1]+1):
                k=(N-i*B[0]-j*B[1])//B[2]
                N=max(M,i*A[0]+j*A[1]+k*A[2]+(N-i-j-k))
    elif len(l)==2:
        for i in range(N//B[l[0]]+1):
            j=(N-i*B[l[0]])//B[l[1]]
            N=max(M,i*A[l[0]]+j*A[l[1]]+(N-i-j))
    elif len(l)==1:
        i=N//B[l[0]]
        N=i*A[l[0]]+N-i
b(l1)
r=list(map(lambda x: -x,r))
b2(l2)
print(N)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
l1=[i for i in range(3) if B[i]>A[i]]
l2=[i for i in range(3) if B[i]<A[i]]
r=[B[i]-A[i] for i in range(3)]
def b(l):
    global N
    if len(l)==3:
        M=0
        for i in range(N//A[0]+1):
            for j in range((N-i*A[0])//A[1]+1):
                k=(N-i*A[0]-j*A[1])//A[2]
                M=max(M,i*B[0]+j*B[1]+k*B[2]+(N-i*A[0]-j*A[1]-k*A[2]))
        N=M
    elif len(l)==2:
        M=0
        for i in range(N//A[l[0]]+1):
            j=(N-i*A[l[0]])//A[l[1]]
            M=max(M,i*B[l[0]]+j*B[l[1]]+(N-i*A[l[0]]-j*A[l[1]]))
        N=M
    elif len(l)==1:
        i=N//A[l[0]]
        N=i*B[l[0]]+N-i*A[l[0]]
def b2(l):
    global N
    if len(l)==3:
        M=0
        for i in range(N//B[0]+1):
            for j in range((N-i*B[0])//B[1]+1):
                k=(N-i*B[0]-j*B[1])//B[2]
                M=max(M,i*A[0]+j*A[1]+k*A[2]+(N-i*B[0]-j*B[1]-k*B[2]))
        N=M
    elif len(l)==2:
        M=0
        for i in range(N//B[l[0]]+1):
            j=(N-i*B[l[0]])//B[l[1]]
            M=max(M,i*A[l[0]]+j*A[l[1]]+(N-i*B[l[0]]-j*B[l[1]]))
        N=M
    elif len(l)==1:
        i=N//B[l[0]]
        N=i*A[l[0]]+N-i*B[l[0]]
b(l1)
r=list(map(lambda x: -x,r))
b2(l2)
print(N)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,A,B,C=map(int,input().split())
pr=10**9+7
def gya(n):
    return pow(n,pr-2,pr)
MAX_NUM = 2*10**5 + 1
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=0
ab=A+B
ap=pow(A,N,pr)
bp=pow(B,N,pr)
abp=1
bap=1
for i in range(N):
    a+=(i+N)*c(N+i-1,N-1)%pr*pow(ab,N-1-i)%pr*(ap*abp+bp*bap)%pr
    abp=abp*B%pr
    bap=bap*A%pr
    a%=pr
a=a*100*gya(pow(ab,2*N,pr))%pr
print(a)

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,A,B,C=map(int,input().split())
pr=10**9+7
def gya(n):
    return pow(n,pr-2,pr)
MAX_NUM = 2*10**5 + 1
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=0
ab=A+B
ap=pow(A,N,pr)
bp=pow(B,N,pr)
abp=1
bap=1
for i in range(N):
    a+=(i+N)*c(N+i-1,N-1)%pr*pow(ab,N-1-i,pr)%pr*(ap*abp+bp*bap)%pr
    abp=abp*B%pr
    bap=bap*A%pr
    a%=pr
a=a*100*gya(pow(ab,2*N,pr))%pr
print(a)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
s=[[]for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
sys.setrecursionlimit(300000)
l=[None]*N
l[0]=0
def hu(n,c):
    for i in s[n]:
        if l[i]==None:
            l[i]=c
            hu(i,c+1)
hu(0,1)
t=l.index(max(l))
l=[None]*N
l[t]=0
hu(t,1)
if max(l)%3==1:
    print("Second")
else:
    print("First")

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
s=[[]for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
sys.setrecursionlimit(300000)
l=[None]*N
l[0]=0
def hu(n,c):
    for i in s[n]:
        if l[i]==None:
            l[i]=c
            hu(i,c+1)
hu(0,1)
t=l.index(max(l))
l=[None]*N
l[t]=0
hu(t,1)
if max(l)%3==1:
    print("Second")
else:
    print("First")
Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
S=input()
L=[]
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        L.append(i+1)
n=len(L)
for i in range(Q):
    l,r=map(int,input().split())
    a=0
    for j in range(n):
        if l<=L[j]<r:
            a+=1
    print(a)

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,Q=map(int, input().split())
S=input()
L=[None]*(N)
t=0
for i in range(N-1):
    L[i]=t
    if S[i]=="A" and S[i+1]=="C":
        t+=1
L[-1]=t
for i in range(Q):
    l,r=map(int,input().split())
    print(L[r-1]-L[l-1])
Buggy python submission (verdict: Runtime Error):
N=int(input())
pr=10**9+7
a=0
l=[0]*N
C=[int(input())-1 for i in range(N)]
for i in range(N-1):
    if C[i]==C[i+1]:
        continue
    a,l[C[i]]=(l[C[i]]+a)%pr,(l[C[i]]+a+1)%pr
a+=l[C[-1]]
print((a+1)%pr)

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
pr=10**9+7
a=0
l=[0]*(2*10**5)
C=[int(input())-1 for i in range(N)]
for i in range(N-1):
    if C[i]==C[i+1]:
        continue
    a,l[C[i]]=(l[C[i]]+a)%pr,(l[C[i]]+a+1)%pr
a+=l[C[-1]]
print((a+1)%pr)

Buggy python submission (verdict: Runtime Error):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
pr=10**9+7
a=0
l=[0]*(N+1)
C=[int(input())-1 for i in range(N)]
for i in range(N-1):
    if C[i]==C[i+1]:
        continue
    a,l[C[i]]=(l[C[i]]+a)%pr,(l[C[i]]+a+1)%pr
a+=l[C[-1]]
print((a+1)%pr)

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
pr=10**9+7
a=0
l=[0]*(2*10**5)
C=[int(input())-1 for i in range(N)]
for i in range(N-1):
    if C[i]==C[i+1]:
        continue
    a,l[C[i]]=(l[C[i]]+a)%pr,(l[C[i]]+a+1)%pr
a+=l[C[-1]]
print((a+1)%pr)

Buggy python submission (verdict: Runtime Error):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
pr=10**9+7
a=0
l=[0]*N
C=[int(input())-1 for i in range(N)]
for i in range(N-1):
    if C[i]==C[i+1]:
        continue
    a,l[C[i]]=(l[C[i]]+a)%pr,(l[C[i]]+a+1)%pr
a+=l[C[-1]]
print((a+1)%pr)

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
pr=10**9+7
a=0
l=[0]*(2*10**5)
C=[int(input())-1 for i in range(N)]
for i in range(N-1):
    if C[i]==C[i+1]:
        continue
    a,l[C[i]]=(l[C[i]]+a)%pr,(l[C[i]]+a+1)%pr
a+=l[C[-1]]
print((a+1)%pr)
Buggy python submission (verdict: Runtime Error):
from math import gcd
N=int(input())
A=list(map(int,input().split()))
g=gcd(A[0],A[1])
for i in range(2,N):
        g=gcd(g,A[i])
print(g)

Fixed submission:
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
g=gcd(A[0],A[1])
for i in range(2,N):
        g=gcd(g,A[i])
print(g)
Buggy python submission (verdict: Runtime Error):
N=int(input())
h=list(map(int,input().split()))
t=[0]*N
a=0
for i in range(N):
        while t[i]<h[i]:
                for j in range(i,N):
                        if t[j]<h[j]:
                                t[j]+=1
                        else:
                                break
                a+=1
print(a)

Fixed submission:
a,b,c=map(int,input().split())
print(a*b//2)
Buggy python submission (verdict: Runtime Error):
H,W=map(int,input().split())
S=[input() for i in range(H)]
l=[[0]*(W+2) for i in range(H+2)]
for i in range(1,H+1):
    for j in range(1,W+1):
        l[i][j]=1
a,c=0,1
def nu(h,w):
    global c,b
    if S[h-1][w-1]=="#":
        b+=1
    if l[h-1][w] and S[h-1][w-1]!=S[h-2][w-1]:
        l[h-1][w]=0
        c+=1
        nu(h-1,w)
    if l[h+1][w] and S[h-1][w-1]!=S[h][w-1]:
        l[h+1][w]=0
        c+=1
        nu(h+1,w)
    if l[h][w-1] and S[h-1][w-1]!=S[h-1][w-2]:
        l[h][w-1]=0
        c+=1
        nu(h,w-1)
    if l[h][w+1] and S[h-1][w-1]!=S[h-1][w]:
        l[h][w+1]=0
        c+=1
        nu(h,w+1)
for i in range(1,H+1):
    for j in range(1,W+2):
        if not l[i][j]:
            continue
        b,c=0,1
        l[i][j]=0
        nu(i,j)
        a+=b*(c-b)
print(a)



Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
H,W=map(int,input().split())
S=[input() for i in range(H)]
l=[[0]*(W+2) for i in range(H+2)]
for i in range(1,H+1):
    for j in range(1,W+1):
        l[i][j]=1
a,c=0,1
def nu(h,w):
    global c,b
    if S[h-1][w-1]=="#":
        b+=1
    if l[h-1][w] and S[h-1][w-1]!=S[h-2][w-1]:
        l[h-1][w]=0
        c+=1
        nu(h-1,w)
    if l[h+1][w] and S[h-1][w-1]!=S[h][w-1]:
        l[h+1][w]=0
        c+=1
        nu(h+1,w)
    if l[h][w-1] and S[h-1][w-1]!=S[h-1][w-2]:
        l[h][w-1]=0
        c+=1
        nu(h,w-1)
    if l[h][w+1] and S[h-1][w-1]!=S[h-1][w]:
        l[h][w+1]=0
        c+=1
        nu(h,w+1)
for i in range(1,H+1):
    for j in range(1,W+2):
        if not l[i][j]:
            continue
        b,c=0,1
        l[i][j]=0
        nu(i,j)
        a+=b*(c-b)
print(a)
Buggy python submission (verdict: Runtime Error):
N,P=map(int,input().split())
if N==1:
    print(P)
else:
    a=1
    for i in range(2,10**6+1):
        s=0
        while True:
            if P%i==0:
                P//=i
                s+=1
            else:
                if s>=N:
                    a*=i**(s//N)
                break
    print(a)


Fixed submission:
N,P=map(int,input().split())
if N==1:
    print(P)
else:
    a=1
    for i in range(2,10**6+1):
        s=0
        while True:
            if P%i==0:
                P//=i
                s+=1
            else:
                if s>=N:
                    a*=i**(s//N)
                break
    print(a)