Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,M,Q=map(int,input().split())
A=[0 for _ in range(N)]
query=[]
for _ in range(Q):
    query.append(tuple(map(int,input().split())))
list=[]
def dfs(v):
    for i in range(int(v[-1]),M):
        nv=v+str(i)
        if len(nv)==N+1:
            list.append(nv)
        else:
            dfs(nv)
dfs("0")
ans=0
for a in list:
    t_ans=0
    for q in query:
        if int(a[q[1]])-int(a[q[0]])==q[2]:
            t_ans+=q[3]
    ans=max(ans,t_ans)
print(ans)

Fixed submission:
N,M,Q=map(int,input().split())
A=[0 for _ in range(N)]
query=[]
for _ in range(Q):
    query.append(tuple(map(int,input().split())))
list=[]
def dfs(v):
    for i in range(int(v[-1]),M):
        nv=v+str(i)
        if len(nv)==N+1:
            list.append(nv)
        else:
            dfs(nv)
dfs("0")
ans=0
for a in list:
    t_ans=0
    for q in query:
        if int(a[q[1]])-int(a[q[0]])==q[2]:
            t_ans+=q[3]
    ans=max(ans,t_ans)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
S=list(input())
R=[0 for _ in range(n)]
G=[0 for _ in range(n)]
B=[0 for _ in range(n)]
r=0;g=0;b=0
for i in range(n):
    if S[i]=="R":
        r+=1 
    if S[i]=="G":
        g+=1
    if S[i]=="B":
        b+=1
    R[i]=r; G[i]=g; B[i]=b
cnt=0
for i in range(n-2):
    for j in range(i,n-1):
        if S[i]==S[j]:
            continue
        if (S[i]=="R" or S[i]=="G") and (S[j]=="R" or S[j]=="G"):
            cnt+=B[-1]-B[j]
            try:
                if S[2*j-i]=="B":
                    cnt-=1
            except:
                pass
        if (S[i]=="G" or S[i]=="B") and (S[j]=="G" or S[j]=="B"):
            cnt+=R[-1]-R[j]
            try:
                if S[2*j-i]=="R":
                    cnt-=1
            except:
                pass
        if (S[i]=="B" or S[i]=="R") and (S[j]=="B" or S[j]=="R"):
            cnt+=G[-1]-G[j]
            try:
                if S[2*j-i]=="G":
                    cnt-=1
            except:
                pass
print(cnt)

Fixed submission:
n=int(input())
S=list(input())
R=[0 for _ in range(n)]
G=[0 for _ in range(n)]
B=[0 for _ in range(n)]
r=0;g=0;b=0
for i in range(n):
    if S[i]=="R":
        r+=1 
    if S[i]=="G":
        g+=1
    if S[i]=="B":
        b+=1
    R[i]=r; G[i]=g; B[i]=b
cnt=0
for i in range(n-2):
    for j in range(i,n-1):
        if S[i]==S[j]:
            continue
        if (S[i]=="R" or S[i]=="G") and (S[j]=="R" or S[j]=="G"):
            cnt+=B[-1]-B[j]
            try:
                if S[2*j-i]=="B":
                    cnt-=1
            except:
                pass
        if (S[i]=="G" or S[i]=="B") and (S[j]=="G" or S[j]=="B"):
            cnt+=R[-1]-R[j]
            try:
                if S[2*j-i]=="R":
                    cnt-=1
            except:
                pass
        if (S[i]=="B" or S[i]=="R") and (S[j]=="B" or S[j]=="R"):
            cnt+=G[-1]-G[j]
            try:
                if S[2*j-i]=="G":
                    cnt-=1
            except:
                pass
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
mod=10**9+7
GCD=[0 for _ in range(K+1)]
for i in range(1,K+1):
    k=K//i
    GCD[i]=(k**N)%mod

ans=0
for i in range(K,0,-1):
    for j in range(2,K//i+1):
        GCD[i]-=GCD[i*j]
    ans+=(GCD[i]*i)%mod
print(ans%mod)

Fixed submission:
N,K=map(int,input().split())
mod=10**9+7
GCD=[0 for _ in range(K+1)]
for i in range(1,K+1):
    GCD[i]=pow(K//i,N,mod)

ans=0
for i in range(K,0,-1):
    for j in range(2,K//i+1):
        GCD[i]-=GCD[i*j]
    ans+=(GCD[i]*i)%mod
print(ans%mod)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
mod=10**9+7
GCD=[0 for _ in range(K+1)]
for i in range(1,K+1):
    k=K//i
    GCD[i]=(k**N)%mod

ans=0
for i in range(K,0,-1):
    for j in range(2,K//i+1):
        GCD[i]-=GCD[i*j]
    ans+=(GCD[i]*i)%mod
print(ans%mod)

Fixed submission:
N,K=map(int,input().split())
mod=10**9+7
GCD=[0 for _ in range(K+1)]
for i in range(1,K+1):
    GCD[i]=pow(K//i,N,mod)

ans=0
for i in range(K,0,-1):
    for j in range(2,K//i+1):
        GCD[i]-=GCD[i*j]
    ans+=(GCD[i]*i)%mod
print(ans%mod)
Buggy python submission (verdict: Time Limit Exceeded):
N,x,y=map(int,input().split())
dp=[[abs(i-k) for k in range(N)]for i in range(N)]
dp[x-1][y-1]=1
dp[y-1][x-1]=1
for k in [x-1,y-1]:
    for i in range(N):
        for j in range(N):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j],abs(i-j))

cnt={}
for k in range(N):
    for i in range(N):
        if dp[k][i] in cnt:
            cnt[dp[k][i]]+=1
        else:
            cnt[dp[k][i]]=1

for i in range(1,N):
    try :
        print(cnt[i]//2)
    except:
        print(0)

Fixed submission:
N,x,y=map(int,input().split())
dp=[[abs(i-k) for k in range(N)]for i in range(N)]
dp[x-1][y-1]=1
dp[y-1][x-1]=1
for k in [x-1,y-1]:
    for i in range(N):
        for j in range(N):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j],abs(i-j))

cnt={}
for k in range(N):
    for i in range(N):
        if dp[k][i] in cnt:
            cnt[dp[k][i]]+=1
        else:
            cnt[dp[k][i]]=1

for i in range(1,N):
    try :
        print(cnt[i]//2)
    except:
        print(0)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)
N=int(input())
abc=list("abcdefghi")
def dfs(s,v):
    global N
    for i in range(v+2):
        ns=s+abc[i]
        if len(ns)<N :
            if i!=v+1:
                dfs(ns,v)
            else:
                dfs(ns,v+1)
        if len(ns)==N:
            print("".join(ns))
if N==1:
    print("a")
else:
    dfs("a",0)

Fixed submission:
#=============================================================================
# パナソニックコンテスト D
#=============================================================================
import sys
sys.setrecursionlimit(10**8)
N=int(input())
abc=list("abcdefghij")
def dfs(s,v):
    global N
    for i in range(v+2):
        ns=s+abc[i]
        if len(ns)<N :
            if i!=v+1:
                dfs(ns,v)
            else:
                dfs(ns,v+1)
        if len(ns)==N:
            print("".join(ns))
if N==1:
    print("a")
else:
    dfs("a",0)

Buggy python submission (verdict: Runtime Error):
N=int(input())
abc=list("abcdefghi")
def dfs(s,v):
    global N
    for i in range(v+2):
        ns=s+abc[i]
        if len(ns)<N :
            if i!=v+1:
                dfs(ns,v)
            else:
                dfs(ns,v+1)
        if len(ns)==N:
            print("".join(ns))
if N==1:
    print("a")
else:
    dfs("a",0)

Fixed submission:
#=============================================================================
# パナソニックコンテスト D
#=============================================================================
import sys
sys.setrecursionlimit(10**8)
N=int(input())
abc=list("abcdefghij")
def dfs(s,v):
    global N
    for i in range(v+2):
        ns=s+abc[i]
        if len(ns)<N :
            if i!=v+1:
                dfs(ns,v)
            else:
                dfs(ns,v+1)
        if len(ns)==N:
            print("".join(ns))
if N==1:
    print("a")
else:
    dfs("a",0)

Buggy python submission (verdict: Runtime Error):
#=============================================================================
# パナソニックコンテスト D
#=============================================================================
N=int(input())
ans=[]

def dfs(s):
    global N
    for i in range(max(s)+2):
        ns=s+[i]
        if len(ns)!=N:
            dfs(ns)
        if len(ns)>N:
            continue
        if len(ns)==N and ns not in ans:
            ans.append(ns)
s=[0]
dfs(s)
abc=list("abcdefghi")
ans.sort()
for item in ans:
    for i in range(N):
        item[i]=abc[item[i]]
    print("".join(item))


Fixed submission:
#=============================================================================
# パナソニックコンテスト D
#=============================================================================
import sys
sys.setrecursionlimit(10**8)
N=int(input())
abc=list("abcdefghij")
def dfs(s,v):
    global N
    for i in range(v+2):
        ns=s+abc[i]
        if len(ns)<N :
            if i!=v+1:
                dfs(ns,v)
            else:
                dfs(ns,v+1)
        if len(ns)==N:
            print("".join(ns))
if N==1:
    print("a")
else:
    dfs("a",0)
Buggy python submission (verdict: Runtime Error):
# ABC 157 C
list_s=[]
list_c=[]
Flag=0
N,M= map(int,input().split())

for i in range(M):
    s,c= map(int,input().split())
    list_s.append(s)
    list_c.append(c)
    if s in list_s:
        x=list_s.index(s)
        n=list_c[x]

        if n!=c:
            Flag=1

if 1 in list_s:
    in1=list_s.index(1)
    n1=list_c[in1]
    if n1==0:
        Flag=1
else :
    n1=1

if 2 in list_s:
    in2=list_s.index(2)
    n2=list_c[in2]
else :
    n2=0

if 3 in list_s:
    in3=list_s.index(3)
    n3=list_c[in3]
else :
    n3=0

if N==1 and n1==0:
    Flag=0
    
if Flag==0:
    if N==1:
        if M==0:
            print(0)
        else:
            print(n1)
    if N==2:
        print(10*n1+n2)
    if N==3:
        print(100*n1+10*n2+n3)
else :
    print(-1)


Fixed submission:
N = int(input())
print((N+1)//2)
Buggy python submission (verdict: Runtime Error):
 N, R = map(int,input().split())
 print(type(N), N, R)

if N<10:
    R=R+100*(10-N)
    print(R)
else:
    print(R)


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


if N<10:
    R=R+100*(10-N)
    print(R)
else:
    print(R)
Buggy python submission (verdict: Time Limit Exceeded):
n,a,b = map(int,input().split())
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

sum=0
for i in range(1,n+1):
    if i==a:
        pass
    elif i==b:
        pass
    else:
        sum+=cmb(n,i)

if sum==0:
    print(0)
else:
    print(sum%(10**9+7))

Fixed submission:
n,a,b=map(int,input().split())
mod=10**9+7
def comb_mod(N,r,mod):
    r=min(n-r,r)
    X=1
    Y=1
    for i in range(r):
        X*=N-i
        Y*=i+1
        X%=mod
        Y%=mod
    return X*pow(Y,mod-2,mod)%mod

ans=(pow(2,n,mod)-1-comb_mod(n,a,mod)-comb_mod(n,b,mod)) % mod
print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
P=list(map(int,input().split()))
E=list()
ans=0
for p in P:
    E.append((1+p)/2)
for i in range(N-K+1):
    ans=max(ans,sum(E[i:i+K]))
print(ans)

Fixed submission:
import queue
N,K=map(int,input().split())
P=list(map(int,input().split()))
que=queue.Queue()
que_tmp=queue.Queue()
ans=0
tmp=0
cnt=0
for p in P:
    if cnt<K:
        que_tmp.put(1+p)
        tmp+=1+p
        cnt+=1
    else:
        que.put(1+p)

while not que.empty():
    dis=que_tmp.get()
    plus=que.get()
    que_tmp.put(plus)
    tmp+=plus-dis
    ans=max(ans,tmp)
print(max(ans,tmp)/2)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
P=list(map(int,input().split()))
E=list()
ans=0
for p in P:
    E.append((1+p)/2)
for i in range(N-K+1):
    ans=max(ans,sum(E[i:i+K]))
print(ans)

Fixed submission:
import queue
N,K=map(int,input().split())
P=list(map(int,input().split()))
que=queue.Queue()
que_tmp=queue.Queue()
ans=0
tmp=0
cnt=0
for p in P:
    if cnt<K:
        que_tmp.put(1+p)
        tmp+=1+p
        cnt+=1
    else:
        que.put(1+p)

while not que.empty():
    dis=que_tmp.get()
    plus=que.get()
    que_tmp.put(plus)
    tmp+=plus-dis
    ans=max(ans,tmp)
print(max(ans,tmp)/2)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
cnt=0
for i in range(1,10):
    for k in range(1,10):
        a=0
        b=0
        for n in range(1,N+1):
            r=n%10
            l=n//(10**(len(str(n))-1))
            if k==r and i==l:
                a+=1
            if i==r and k==l:
                b+=1
        cnt+=a*b
print(cnt)

Fixed submission:
N=int(input())
cnt=0
for i in range(1,10):
    for k in range(1,10):
        a=0
        b=0
        for n in range(1,N+1):
            r=n%10
            l=n//(10**(len(str(n))-1))
            if k==r and i==l:
                a+=1
            if i==r and k==l:
                b+=1
        cnt+=a*b
print(cnt)
Buggy python submission (verdict: Runtime Error):
a,b=map(int, input().split())
total=500*a
if total=>X:
  print("Yes")
else:
  print("No")

Fixed submission:
a,b=map(int, input().split())
total=500*a
if total>=b:
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
total=500*k
if total=>X:
  print("Yes")
else:
  print("No")
  

Fixed submission:
a,b=map(int, input().split())
total=500*a
if total>=b:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
#=============================================================================
#ABC150 D
#=============================================================================
import fractions
from functools import reduce

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

lcm = 1
for A in a:
    a//=2
    lcm *=a//fractions.gcd(lcm, a)
    if lcm>0:
        print(0)
        exit()
for A in a:
    if lcm/A==int(lcm/A):
        print(0)
        exit()

cnt=M//lcm
print((cnt+1)//2)


Fixed submission:
#=============================================================================
#ABC150 D
#=============================================================================
import fractions
from functools import reduce

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

lcm = 1
for A in a:
    A//=2
    lcm *=A//fractions.gcd(lcm, A)
    if lcm>M:
        print(0)
        exit()
for A in a:
    if lcm/A==int(lcm/A):
        print(0)
        exit()

cnt=M//lcm
print((cnt+1)//2)

Buggy python submission (verdict: Runtime Error):
#=============================================================================
#ABC150 D
#=============================================================================
import fractions
from functools import reduce

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

lcm = a[0]//2
for i in range(1, N):
    x=a[i]//2
    lcm = lcm * x // fractions.gcd(lcm, a[i])
for A in a:
    if lcm/A==int(lcm/A):
        print(0)
        exit()

cnt=M//lcm
print((cnt+1)//2)

Fixed submission:
#=============================================================================
#ABC150 D
#=============================================================================
import fractions
from functools import reduce

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

lcm = 1
for A in a:
    A//=2
    lcm *=A//fractions.gcd(lcm, A)
    if lcm>M:
        print(0)
        exit()
for A in a:
    if lcm/A==int(lcm/A):
        print(0)
        exit()

cnt=M//lcm
print((cnt+1)//2)
Buggy python submission (verdict: Runtime Error):
N=int(input())
S=input()
if N%2==0:
  if S[:N/2]==S[N/2:]:
    print("Yes")
    exit()
print("No")

Fixed submission:
N=int(input())
S=input()
if N%2==0:
  if S[:int(N/2)]==S[int(N/2):]:
    print("Yes")
    exit()
print("No")
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
if a>9 or b>9:
  pritn(-1)
else:
  print(a*b)

Fixed submission:
a,b=map(int,input().split())
if a>9 or b>9:
  print(-1)
else:
  print(a*b)
Buggy python submission (verdict: Runtime Error):
mport math

def prime_function(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    
    f=3
    while f*f<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return a

A,B=map(int,input().split())
GCD=math.gcd(A,B)
print(len(set(prime_function(GCD)))+1)







Fixed submission:
import fractions

def prime_function(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    
    f=3
    while f*f<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return a

A,B=map(int,input().split())
GCD=fractions.gcd(A,B)
print(len(set(prime_function(GCD)))+1)
Buggy python submission (verdict: Time Limit Exceeded):
import re
N=int(input());S=input()

def same_check(index,number):
    while index-number>=0:
        pattern=S[index-number:index+1]
        match_list=re.findall(pattern,S[:index+1])
        if len(match_list)==1:
            return number
        else:
            number+=1

number=0
for i in range(N):
    number=same_check(i,number)
print(number)

Fixed submission:
n=int(input());s=input()

a=0
i=0
j=1
while j<n:
    if s[i:j] in s[j:]:
        a=max(a,j-i)
        j+=1
    else:
        i+=1

    if i==j:
        i+=1
        j+=2
print(a)

Buggy python submission (verdict: Time Limit Exceeded):
import re
N=int(input());S=input()

def same_check(index,number):
    while index-number>=0:
        pattern=S[index-number:index+1]
        match_list=re.findall(pattern,S[:index+1])
        if len(match_list)==1:
            return number
        else:
            number+=1

number=0
for i in range(N):
    number=same_check(i,number)
print(number)

Fixed submission:
n=int(input());s=input()

a=0
i=0
j=1
while j<n:
    if s[i:j] in s[j:]:
        a=max(a,j-i)
        j+=1
    else:
        i+=1

    if i==j:
        i+=1
        j+=2
print(a)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline 
n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
ans=[0 for _ in range(n+1)]
seen=[False for _ in range(n+1)]

for _ in range(n-1):
    a,b=map(int,input().split())
    Graph[a].append(b)
    Graph[b].append(a)

for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

def dfs(v):
    seen[v]=True
    for nv in Graph[v]:
        if seen[nv]:
            continue
        else:
            ans[nv]+=ans[v]
            dfs(nv)

dfs(1)
print(*ans[1:])

Fixed submission:
a=int(input())
s=input()

if a>=3200:
    print(s)
else:
    print("red")
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
strings=sorted([sorted(list(input())) for i in range(N)])
cnt=0
for i in range(N-1):
    for k in range(1,N-i):
        if strings[i]==strings[i+k]:
            cnt+=1
        else:
            break
print(cnt)

Fixed submission:
N=int(input())
strings=sorted([sorted(list(input())) for i in range(N)])
strings.append("000")
cnt=0
i=0
same=1
while i<N:
    if strings[i]==strings[i+1]:
        same+=1
    else:
        cnt+=same*(same-1)/2
        same=1
    i+=1
print(int(cnt))

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
strings=sorted([sorted(list(input())) for i in range(N)])
cnt=0
for i in range(N-1):
    for k in range(1,N-i):
        if strings[i]==strings[i+k]:
            cnt+=1
        else:
            break
print(cnt)

Fixed submission:
N=int(input())
strings=sorted([sorted(list(input())) for i in range(N)])
strings.append("000")
cnt=0
i=0
same=1
while i<N:
    if strings[i]==strings[i+1]:
        same+=1
    else:
        cnt+=same*(same-1)/2
        same=1
    i+=1
print(int(cnt))
Buggy python submission (verdict: Runtime Error):
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
color=[]
A=A[::-1]
for a in A:
    i=bisect.bisect_left(color,a)
    if i==len(color):
        color.append(a)
    else:
        color[i]=a
print(len(color))

Fixed submission:
r=int(input())
print(3*r**2)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
for n in range(N,0,-1):
    if A[n-1]==1:
        B[n-1]=1
        for x in range(1,int(n**0.5)+1):
            if n%x==0:
                if x**2==n:
                    A[x-1]=(A[x-1]+1)%2
                else:
                    y=n//x
                    A[x-1]=(A[x-1]+1)%2
                    A[y-1]=(A[y-1]+1)%2
print(sum(B))
for i in range(N):
    if B[i]==1:
        print(i+1,end=" ")

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
for n in range(N,0,-1):
    if A[n-1]==1:
        B[n-1]=1
        for x in range(1,int(n**0.5)+1):
            if n%x==0:
                if x**2==n:
                    A[x-1]=(A[x-1]+1)%2
                else:
                    y=n//x
                    A[x-1]=(A[x-1]+1)%2
                    A[y-1]=(A[y-1]+1)%2
print(sum(B))
for i in range(N):
    if B[i]==1:
        print(i+1,end=" ")
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
color=[]
for a in A:
    i=bisect.bisect_left(color,a)
    if i==0:
        color.append(a)
    else:
        color[i-1]=a
    color.sort()
print(len(color))

Fixed submission:
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
color=[]
A=A[::-1]
for a in A:
    i=bisect.bisect_right(color,a)
    if i==len(color):
        color.append(a)
    else:
        color[i]=a
print(len(color))

Buggy python submission (verdict: Runtime Error):
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
color=[]
for a in A:
    i=bisect.bisect_left(color,a)
    if i==0:
        color+=[a]
    else:
        color[i]=a
        color.sort()
print(len(color))

Fixed submission:
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
color=[]
A=A[::-1]
for a in A:
    i=bisect.bisect_right(color,a)
    if i==len(color):
        color.append(a)
    else:
        color[i]=a
print(len(color))
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
mod=1000000007
f=[False]*(N+1)
for _ in range(M):
    i=int(input())
    f[i]=True
dp=[0 for _ in range(N+1)]

if f[1] and f[2]:
    print(0)
    exit()
elif f[1]:
    dp[1]=0;dp[2]=1
elif f[2]:
    dp[1]=1;dp[2]=0
else:
    dp[1]=1;dp[2]=2

for i in range(3,N+1):
    if f[i]:
        dp[i]=0
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[N]%mod)

Fixed submission:
N,M=map(int,input().split())
mod=1000000007
f=[False]*(N+1)
for _ in range(M):
    i=int(input())
    f[i]=True
dp=[0 for _ in range(N+1)]

if N==1:
    if f[1]:
        print(0)
    else:
        print(1)
else:
    if f[1] and f[2]:
        print(0)
        exit()
    elif f[1]:
        dp[1]=0;dp[2]=1
    elif f[2]:
        dp[1]=1;dp[2]=0
    else:
        dp[1]=1;dp[2]=2

    for i in range(3,N+1):
        if f[i]:
            dp[i]=0
        else:
            dp[i]=dp[i-1]+dp[i-2]
    print(dp[N]%mod)
Buggy python submission (verdict: Runtime Error):
#
import sys
sys.setrecursionlimit(10**7)

N=int(input())
Graph=[[] for _ in range(N)]
color=[-1]*N

for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    Graph[a].append((b,c))
    Graph[b].append((a,c))

def dfs(v,cur=0):
    color[v]=cur
    for next_v,w in Graph[v]:
        if color[next_v]==-1:
            if w%2==1:
                cur=1-cur
        dfs(next_v,cur)
#探索
dfs(0)
for i in color:
    print(i)


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

N=int(input())
Graph=[[] for _ in range(N)]
color=[-1]*N

for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    Graph[a].append((b,c))
    Graph[b].append((a,c))

def dfs(Graph,v,cur=0):
    global color
    color[v]=cur
    for next_v_t in Graph[v]:
        next_v=next_v_t[0]
        w=next_v_t[1]
        if color[next_v]!=-1:
            continue
        ncur=cur
        if w%2==1:
            ncur=1-cur
        dfs(Graph,next_v,ncur)

#探索
for v in range(N):
    if color[v]==-1:
        dfs(Graph,v)
for i in color:
    print(i)