Harryxun/stf_run huggingface dataset:
from collections import defaultdict as dd
N, C = tuple(map(int, input().split()))
events = []
tmax = 0
dic=dd(list)
for i in range(N):
    s, t, c = map(int, input().split())
    dic[c].append((s,t))
eps = 0.5
for k,v in dic.items():
    v1 = sorted(v)
    lev = len(v)
    prev = [-1,-1]
    for i,val in enumerate(v1):
        if tmax < val[1]:
            tmax = val[1]
        if prev == [-1,-1]:
            prev[0] = val[0]
            prev[1] = val[1] # end_time
            if lev != 1:
                continue
            else:
                events.append((prev[0]-eps, 1))
                events.append((prev[1], 0))
                break
        if i==lev-1:
            events.append((prev[0]-eps, 1))
            events.append((prev[1], 0))
            break
        if prev[1] == val[0]:# prev_end == now_start
            prev[1] = val[1]
        else:
            events.append((prev[0]-eps, 1))
            events.append((prev[1], 0))
            prev = val
events.sort()
idx = 0
cnt = 0
res = 0
events.append((0,-1))
for t in range(tmax + 1):
    while events[idx][0] <= t:
        event = events[idx]
        if event[1] == 1:
            cnt += 1
            if res < cnt:
                res = cnt
        elif event[1] == 0:
            cnt -= 1
        else:
            break
        idx += 1
print(res)

### FIXED CODE ###

from collections import defaultdict as dd
N, C = tuple(map(int, input().split()))
events = []
tmax = 0
dic=dd(list)
for i in range(N):
    s, t, c = map(int, input().split())
    dic[c].append((s,t))
eps = 0.5
for k,v in dic.items():
    v1 = sorted(v)
    lev = len(v1)
    prev = [-1,-1]
    for i,val in enumerate(v1):
        if tmax < val[1]:
            tmax = val[1]
        if prev == [-1,-1]:
            prev[0] = val[0]
            prev[1] = val[1] # end_time
            if lev != 1:
                continue
            else:
                events.append((prev[0]-eps, 1))
                events.append((prev[1], 0))
                break
        if prev[1] == val[0]:# prev_end == now_start
            prev[1] = val[1]
            if i == lev - 1:
                events.append((prev[0] - eps, 1))
                events.append((prev[1], 0))
                break
        else:
            events.append((prev[0]-eps, 1))
            events.append((prev[1], 0))
            prev[0] = val[0]
            prev[1] = val[1]
            if i==lev-1:
                events.append((val[0]-eps, 1))
                events.append((val[1], 0))
                break
events.sort()
idx = 0
cnt = 0
res = 0
events.append((0,-1))
for t in range(tmax + 1):
    while events[idx][0] <= t:
        event = events[idx]
        if event[1] == 1:
            cnt += 1
            if res < cnt:
                res = cnt
        elif event[1] == 0:
            cnt -= 1
        else:
            break
        idx += 1
print(res)
base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()

    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = e * base + f[i]
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
h = dict()
while q:
    p = [ord(c) for c in input().strip()]
    pl = len(p)
    key = calc_hash(p, pl, pl).pop() & mask
    if pl in h:
        haystack = h[pl]
    else:
        haystack = calc_hash(t, pl, tl)
        h[pl] = haystack
    print(1 if key in haystack else 0)
    q -= 1

### FIXED CODE ###

base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()

    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
ps = [input().strip() for _ in range(q)]
h = dict()
a = []
hash_len = 19
for p in ps:
    p = [ord(c) for c in p]
    pl = len(p)
    if pl > tl:
        a.append(0)
        continue
    bs = min(hash_len, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    a.append(1 if keys.issubset(h[bs]) else 0)
print('\n'.join(map(str, a)))
a = int(input())
if(a > = 30):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a = int(input())
if(a >= 30):
  print("Yes")
else:
  print("No")
if a * b %= 0:
  print('Even')
else:
  print('Odd')

### FIXED CODE ###

a, b = map(int, input().split())
if a * b % 2 == 0:
  print('Even')
else:
  print('Odd')
cord = list(input())
cord_len = len(cord)
for i in range(cord - 1):
    if cord[i] == cord[i + 1]:
        print("Bad")
        break
else:
    print("Good")


### FIXED CODE ###

cord = list(input())
cord_len = len(cord)
for i in range(cord_len - 1):
    if cord[i] == cord[i + 1]:
        print("Bad")
        break
else:
    print("Good")
H,A = map(int(),input().split)
print(H//A if H%A == 0 else H//A+1)


### FIXED CODE ###

H,A = map(int,input().split())
print(H//A if H%A == 0 else H//A+1)
from collections import deque
import collections
from scipy.special import comb

N = int(input())
A = list(map(int, input().split()))
d2 = deque()
d = deque(A)
ans = 0

for i in range(N):
    d2.append(d.popleft())
    if i > 0:
        d.append(d2.popleft())
    c = collections.Counter(d)
    for i in c.keys():
        if c[i] >= 2:
            ans += comb(c[i], 2)
    print(int(ans))
    ans =0


### FIXED CODE ###

import collections

N = int(input())
A = list(map(int, input().split()))

c = collections.Counter(A)
keys = c.keys()
comb = 0
for i in keys:
    comb += (c[i] * (c[i]-1)) //2

for i in A:
    ans = comb - (c[i]-1)
    print(ans)
n=int(input())
arr=list(map(int,input().split()))+[0]
arr=sorted(arr, reverse=True
ans1=0
ans2=0
count=1
for i in range(n):
  if arr[i]!=arr[i+1]:
    if count>=2:
      if ans1==0:
        ans1=arr[i]
      else:
        ans2=arr[i]
    count=1
  else:
    count+=1
print(ans1*ans2)

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))+[0]
arr=sorted(arr, reverse=True)
ans1=0
ans2=0
ans3=0
count=1
for i in range(n):
  if arr[i]!=arr[i+1]:
    if count>=2:
      if ans1==0:
        ans1=arr[i]
      elif ans2==0:
        ans2=arr[i]      
      if count>=4:
        if ans3==0:
          ans3=arr[i]
    count=1
  else:
    count+=1
print(max(ans1*ans2,ans3**2))
list1=[]
num=int(input())
for i in range (0,num):
	some=input()
    list1.append(some)
print(len(set(i for i in list1 if i.isalpha())))

### FIXED CODE ###

list1=[]
num=int(input())
for i in range (0,num):
    list1.append(input())
print(len(set(i for i in list1 if i.isalpha())))
n, m = map(int, input().split())
ans = []
tmp = True
for i in range(n): ans.append('a')

for i in range(m):
    s, c = map(int, input().split())

    if s == 1 and c == 0:
        tmp = False
        break

    if s > n:
        tmp = False
        break

    if c < 0 or c > 9:
        tmp = False
        break

    if ans[s - 1] == 'a':
        ans[s - 1] = str(c)
    else:
        if ans[s - 1] != str(c):
            tmp = False
            break

if ans[0] == a: ans[0] = '1'
for i in range(n):
    if ans[i] == a: ans[i] = '0'

if tmp:
    for i in range(n):
        print(ans[i], end='')
    print()
else:
    print('-1')



### FIXED CODE ###

n, m = map(int, input().split())
ans = []
tmp = True
for i in range(n): ans.append('a')

for i in range(m):
    s, c = map(int, input().split())

    if s < 1 or s > n:
        tmp = False
        break
    if c < 0 or c > 9:
        tmp = False
        break

    if n != 1 and s == 1 and c == 0:
        tmp = False
        break

    if ans[s - 1] == 'a':
        ans[s - 1] = str(c)
    else:
        if ans[s - 1] != str(c):
            tmp = False
            break

if n != 1 and ans[0] == 'a': ans[0] = '1'
for i in range(n):
    if ans[i] == 'a': ans[i] = '0'

if tmp:
    for i in range(n):
        print(ans[i], end='')
    print()
else:
    print(-1)
a, b =  (int(x) for x in input.split())

if a > 9 or b > 9 :
  print(-1)
else :
  print(a*b)


### FIXED CODE ###

a, b =  (int(x) for x in input().split())
if a > 9 or b > 9 :
  print('-1')
else :
  print(a*b)
L = int(input().split())

print((L**3)/27)

### FIXED CODE ###

L = int(input())

print((L**3)/27)
import math
a,b,h,m=list(map(int, input().split()))


th_a = 360/12 * h + 360/12*m/60
th_b = 360*m/60
print(th_a)
print(th_b)
ab_th = abs(th_a - th_b)
if ab_th > 180:
    ab_th = 360 - ab_th

print(math.sqrt(a*a + b*b -2*a*b*math.cos(math.radians(ab_th))))

### FIXED CODE ###

x = input()
l = [2,4,5,7,9]
i = [0,1,6,8]
if int(x[-1]) in l:
    print("hon")
elif int(x[-1]) in i:
    print("pon")
elif x[-1] == "3":
    print("bon")
a,b,k=map(int,input().split())
c=100,d=0
while d<k:
  if a%c==0 and b%c==0:
    d+=1
  c-=1
print(c+1)


### FIXED CODE ###

a,b,k=map(int,input().split())
c=100
d=0
while d<k:
  if a%c==0 and b%c==0:
    d+=1
  c-=1
print(c+1)
s=input()
t=s
s_list=list(s)
for i in range(len(t)):
    if t[i]=='?':
        
        if t[i-1]=='D':
            if i==len(t):
                s_list[i]='D'
            if t[i+1]=='P':
                s_list[i]='D'
            else:
                s_list[i]='P'
          
        else:
            s_list[i]='D'
    
s_cha="".join(s_list)            
print(s_cha)            


### FIXED CODE ###

s=input()
t=s
s_list=list(s)
for i in range(len(t)):
    if s_list[i]=='?':
        
        
        if s_list[i-1]=='D':
            if i==len(t)-1:
                s_list[i]='D'
            elif s_list[i+1]=='P':
                s_list[i]='D'
            elif s_list[i+1]=='D':
                s_list[i]='P'
            else:
                s_list[i]='P'
          
        else:
            s_list[i]='D'
    
s_cha="".join(s_list)            
print(s_cha)
from collections import deque
import sys
sys.setrecursionlimit(100000000)
 
h,w=map(int, input().split())  
s=[list(input()) for i in range(h)]
v=[]
def bfs():
    d = [[float("inf")] * w for i in range(h)]
    que = deque([])
    #黒だったらスタートキューに入れる
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                que.append((i, j))
                d[i][j]=0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    
    while que:
        p = que.popleft()
         # 黒にする4方向をループ
        for i in range(4):
            ny = p[0] + dx[i]
            nx = p[1] + dy[i]
 
            if 0<=nx<w and 0<=ny<h and d[nx][ny] == float("inf"):
                que.append((ny, nx))
                d[nx][ny] = d[p[0]][p[1]] + 1
                
    for i in range(h):
        v.append(max(d[i]))
    return max(v)
res=bfs()
print(res)
        


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
s = [input() for i in range(h)]

d = [[h+w for j in range(w)] for i in range(h)]
que = deque()

#黒だったらスタートキューに入れる
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
        que.append((i, j))
        d[i][j] = 0

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


while que:
    p = que.popleft()
    # 黒にする4方向をループ
    for i in range(4):
        nx = p[1] + dx[i]
        ny = p[0] + dy[i]

        if (0<=nx<w) and (0<=ny<h) and (d[ny][nx]==h+w):
            que.append((ny, nx))
            d[ny][nx] = d[p[0]][p[1]] + 1

res = max(map(max, d))
print(res)
x = list(map(int,input().split()))
 
for i in range(len(x)):
	IF x[i] == 0:
    	print(i+1)
    	break


### FIXED CODE ###

x = list(map(int,input().split()))
 
for i in range(len(x)):
  if x[i] == 0:
    print(i+1)
    break
N, A, B = map(int, input().split())
H = [int(input()) for _ in range(N)]

l = 0
r = max(H)

while r > l+1:
    T = (l+r)//2
    c = 0
    for h in H:
        if h > B*T:
            c += (h-B*T)//(A-B)
            if (h-B*T)%(A-B) != 0:
                c += 1
    if c <= T:
        r = T
    else:
        l = T

if l == T:
    print(T+1)
else:
    print(T)

### FIXED CODE ###

N, A, B = map(int, input().split())
H = [int(input()) for _ in range(N)]

l = 0
r = max(H)
T = 1
while r > l+1:
    T = (l+r)//2
    c = 0
    for h in H:
        if h > B*T:
            c += (h-B*T)//(A-B)
            if (h-B*T)%(A-B) != 0:
                c += 1
    if c <= T:
        r = T
    else:
        l = T

if l == T:
    print(T+1)
else:
    print(T)
n, k = map(int, raw_input().split())
s = list(raw_input())
s[k] = s[k].lower()
ans = ""
for i in s:
  ans = ans + i
print ans

### FIXED CODE ###

n, k = map(int, raw_input().split())
s = list(raw_input())
s[k - 1] = s[k - 1].lower()
ans = ""
for i in s:
  ans = ans + i
print ans
H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    for j in range(W):
        if s[j] == '.':
            s[j] = 0
    S.append(s)

dx = [0,1,1,1,0,-1,-1,-1]
dy = [1,1,0,-1,-1,-1,0,1]
for i in range(H):
    for j in range(W):
        for k in range(8):
            nx = j + dx[k]
            ny = i + dy[k]
            if nx >= 0 and ny >= 0 and ny < H and nx < W:
                if S[ny][nx] == "#":
                    S[i][j] += 1
for i in range(H):
    l = map(str,S[i])
    ans = "".join(l)
    print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    for j in range(W):
        if s[j] == '.':
            s[j] = 0
    S.append(s)

dx = [0,1,1,1,0,-1,-1,-1]
dy = [1,1,0,-1,-1,-1,0,1]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        for k in range(8):
            nx = j + dx[k]
            ny = i + dy[k]
            if nx >= 0 and ny >= 0 and ny < H and nx < W :
                if S[ny][nx] == "#":
                    S[i][j] += 1
for i in range(H):
    l = map(str,S[i])
    ans = "".join(l)
    print(ans)
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]

A.sort()
BC.sort(key=lambda x:x[1], reverse=True)
pos = 0
for b, c in BC:
    for i in range(pos, pos + b):
        if A[i] < c:
            A[i] = c
        else:
            break
    pos = i + 1

print(sum(A))

### FIXED CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]

A.sort()
BC.sort(key=lambda x:x[1], reverse=True)

pos = 0
for b, c in BC:
    end = (pos + b) if pos + b <= n else n
    for i in range(pos, end):
        if A[i] < c:
            A[i] = c
        else:
            break
    pos = i + 1
    if pos >= n:
        break

print(sum(A))
x,y = input().split()
if x>y:
  print('>')
elif x=y:
  print('=')
else:
  print('<')

### FIXED CODE ###

x,y = input().split()
if x>y:
  print('>')
elif x==y:
  print('=')
else:
  print('<')
N=int(input())
M=int(input())
S=str(N)
A=len(S)
int(S[i])
for i in range(A):
　　M=M+S[i]
if M%9==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N=int(input())
if N%9==0:
  print("Yes")
else:
  print("No")
a, b = input().split())
ab=int(a + b)

i=1
while True:
    ii=i * i
    if ab == ii:
        print("Yes")
        break

    if ii > ab:
        print("No")
        break
    i += 1


### FIXED CODE ###

a, b = input().split()
ab=int(a + b)

i=1
while True:
    ii=i * i
    if ab == ii:
        print("Yes")
        break

    if ii > ab:
        print("No")
        break
    i += 1
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
n = int(input())
listA=list(map(int, input().split()))
print(gcd_list(listA))
            

### FIXED CODE ###

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
n = int(input())
listA=list(map(int, input().split()))
print(gcd_list(listA))
N = input()
str = input().split()
H = []
for i range(N):
  H[i] = str[i]
flag = []
for i range(N):
  for j range(i):
    if H [i] < H[j]:
      flag[i] = 1
    else:
      flag[i] = 0
ans = 0
for i range(N):
  if flag[i] = 0:
    ans = ans+1
print(ans)
    

### FIXED CODE ###

N = input()
N = int(N)
str = input().split()
H = []
i = 0
j = 0
for i in range(N):
  H.append( int(str[i]) )
flag = 0
ans = 0
for i in range(N):
  for j in range(i):
    if H [i] < H[j]:
      flag =  1
      break
    else:
      flag = 0
  if flag == 0:
    ans = ans+1
  flag = 0

print(ans)
from bisect import bisect_left
import string 

dic={c:[] for c in string.ascii_lowercase}
N=int(input())
S=list(input())
Q=int(input())
for i in range(len(S)):
  dic[S[i]].append(i+1)
for i in range(Q):
  a,b,c=map(str,input().split())
  if a=='1':
    if S[int(b)-1]==c:
      continue
    d=bisect_left(dic[S[int(b)-1]],int(b))
    e=bisect_left(dic[c],int(b))
    dic[S[int(b)-1]].pop(d)
    dic[c].insert(e,int(b))
  else:
    ans=0
    b,c=int(b),int(c)
    for j in string.ascii_lowercase:
      d=bisect_left(dic[j],b)
      if d<len(dic[j]):
        if dic[j][d]<=c:
          ans+=1
    print(ans)

### FIXED CODE ###

from bisect import bisect_left,bisect_right
import string 

dic = {c:[] for c in string.ascii_lowercase}

n = int(input())
s = list(input())
q = int(input())

for i,c in enumerate(s,start=1):
  dic[c].append(i)
  
for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    if r == s[j-1]:
      continue
    c = s[j-1]    
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    l = int(l)
    r = int(r)
    for c in string.ascii_lowercase:
      pl = bisect_left(dic[c],l)
      if pl < len(dic[c]):
        if dic[c][pl] <= r:
          ans += 1
    print(ans)
def beautiful:
      a,b,c = int(input()).split()
      if ((abs(b-a)) == (abs(c-b))):
            print('YES')
      else:
            print('NO')

beautiful()

### FIXED CODE ###

a,b,c= map(int, input().split())
if ((a+c)==b*2):
 print('YES')
else:
 print('NO')
a, b = map(int, raw_input().split())

  if a > b:
    print 'a > b'
  elif a < b:
    print 'a < b'
  else:
    print 'a == b'

### FIXED CODE ###

a, b = map(int, raw_input().split())

if a > b:
  print 'a > b'
elif a < b:
  print 'a < b'
else:
  print 'a == b'
N, K = map(int, input().split())
import math
mod =10**9+7

l = []
for i in range(K):
  a = math.factorial(N-K+1)//(math.factorial(N-K-i)*math.factorial(i+1))
  b = math.factorial(K-1)//(math.factorial(K-1-i)*math.factorial(i))
  ans = int(a)*int(b)
  l.append(int(ans))

for j in l:
  print(j%mod)


### FIXED CODE ###

N, K = map(int, input().split())
import math
mod =10**9+7

l = []
l.append(N-K+1)
for i in range(1, K):
  a = l[i-1] * (N-K-i+1) * (K-i) // ((i+1)*i)
  l.append(int(a))

for j in l:
  print(j%mod)
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

m = a[0]
k = b[0]
for i in range(n):
    if a[i] >b[i] :
        ans += a[i]-b[i]
print(ans)

### FIXED CODE ###

A,B=map(int, input().split())
if A>B:
  print(2*A-1)
elif A==B:
  print(2*A)
else:
  print(2*B-1)
A,B = map(int,input().split)
if A*B > A+B|A-B : ans = A*B
if A+B > A-B|A*B : ans = A+B
if A-B > A*B|A+B : ans = A-B
print(ans)

### FIXED CODE ###

A,B = map(int,input().split())
X = A + B
Y = A - B
Z = A * B
if X >= Y and X >= Z:
     print(X)
elif Y >= Z and Y >= X:
     print(Y)
elif Z >= X and Z >= Y:
     print(Z)
import sys
import math
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
  sys.exit()
n=(x+y)//3
print(math_factorial(n)//math_factorial(x-n)//math_factorial(y-n))

### FIXED CODE ###

import sys
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
  sys.exit()
n=(x+y)//3

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

print(cmb(n,x-n,mod))
from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    common = lcm_list(A)
    max_A = max(A)
    cnt = M // common
    if (cnt + 0.5) * common <= M:
        if max_A * 0.5 <= common * 0.5:
            print(cnt + 1)
        else:
            print(cnt)
    else:
        if max_A * 0.5 <= common * 0.5:
            print(cnt)
        else:
            print(cnt - 1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def cnt_div_2(x):
    cnt = 0
    while x > 0:
        if x % 2 == 0:
            x //= 2
            cnt += 1
        else:
            break
    return cnt

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    cnt_2 = cnt_div_2(A[0])
    for a in A:
        if cnt_div_2(a) != cnt_2:
            print(0)
            exit()


    common = lcm_list(A)
    max_A = max(A)
    cnt = M // common
    if ((2 * cnt + 1) * common) // 2 <= M:
        print(cnt + 1)
    else:
        print(cnt)
    
if __name__ == "__main__":
    main()
import sys
sys.setrecursionlimit(10**9)

MOD = 10**9 + 7
N = int(input())
paths = {i:[] for i in range(N+1)}
for _ in range(N-1):
    x, y = map(int, input().split())
    paths[x].append(y)
    paths[y].append(x)

dpt = [[[-1] * 2 for i in range(N+1)] for j in range(N+1)]

def count_cc(prev, node, color):
    if dpt[prev][node][color] != -1:
        return dpt[prev][node][color]
    if paths[node] == [prev]:
        dpt[prev][node][color] = 1
        return 1
    result = 1
    if color == 0:
        for nxt in paths[node]:
            if nxt == prev:
                continue
            result *= (count_cc(node, nxt, 0) + count_cc(node, nxt, 1))
            result %= MOD
    else:
        for nxt in paths[node]:
            if nxt == prev:
                continue
            result *= count_cc(node, nxt, 0)
            result %= MOD

    dpt[prev][node][color] = result
    return result

print(count_cc(0, 2, 0) + count_cc(0, 2, 1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

MOD = 10**9 + 7
N = int(input())
paths = {i:[] for i in range(N+1)}
for _ in range(N-1):
    x, y = map(int, input().split())
    paths[x].append(y)
    paths[y].append(x)

dpt = [[-1] * 2 for i in range(N+1)]

def count_cc(prev, node, color):
    if dpt[node][color] != -1:
        return dpt[node][color]
    if paths[node] == [prev]:
        dpt[node][color] = 1
        return 1
    result = 1
    if color == 0:
        for nxt in paths[node]:
            if nxt == prev:
                continue
            result *= (count_cc(node, nxt, 0) + count_cc(node, nxt, 1))
            result %= MOD
    else:
        for nxt in paths[node]:
            if nxt == prev:
                continue
            result *= count_cc(node, nxt, 0)
            result %= MOD

    dpt[node][color] = result
    return result

print((count_cc(0, 1, 0) + count_cc(0, 1, 1)) % MOD)