Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10 ** 7)

def solve(g, p, index, y, z, k):
    p[index] = k - y - z
    x = 1
    for i in g[index]:
        if p[i] == -1:
            solve(g, p, i, x, y, k)
            y += 1

def main():
    n, k = map(int, input().split())
    graph =[[] for _ in range(n)]
    p = [-1]*n
    for _ in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    s = None
    for i in range(n):
        if len(graph[i]) == 1:
            s = i
            break
    solve(graph, p, s, 0, 0, k)
    ans = 1
    for i in p:
        ans *= i
        ans %= 10**9 + 7
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

def solve(g, p, index, y, z, k):
    p[index] = k - y - z
    x = 1
    for i in g[index]:
        if p[i] == -1:
            solve(g, p, i, x, y, k)
            y += 1

def main():
    n, k = map(int, input().split())
    graph =[[] for _ in range(n)]
    p = [-1]*n
    for _ in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    s = None
    for i in range(n):
        if len(graph[i]) == 1:
            s = i
            break
    if s is None:
        print(k)
        sys.exit()
    solve(graph, p, s, 0, 0, k)
    ans = 1
    for i in p:
        ans *= i
        ans %= 10**9 + 7
    print(ans)

if __name__ == "__main__":
    main()
import re
a,b=map(int,input().split())
s=input()
if re.fullmatch('^[0-9]{a}-[0-9]{b}$',s)==True:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

a,b=map(int,input().split())
s=input()
if s[a]=='-' and s.count('-')==1:
  print('Yes')
else:
  print('No')
N, M = map(int, input().split())
A = map(int, input().split())

cnt = 0
cnt1 = 0

for i in range(N):
    cnt = cnt + A[i]

for i in range(N):
    if A[i] / cnt > 1 / 4 / M:
        cnt1 = cnt1 + 1

if cnt1 > M:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

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



cnt = 0
cnt1 = 0

for i in range(N):
    cnt = cnt + A[i]

for i in range(N):
    if A[i] / cnt >= 1 / 4 / M:
        cnt1 = cnt1 + 1



if cnt1 >= M:
    print('Yes')
else:
    print('No')
import sys
S = [ord(i) for i in input()]
T = [ord(j) for j in input()]
S.sort()
T.sort()
for k in range(len(S)):
  if S[k] > T[k]:
    print("No")
    sys.exit()
  elif S[k] < T[k]:
    print("Yes")
    sys.exit()
  else:
    None
if len(S) <= len(T):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

import sys
S = "".join(sorted(input()))
T = "".join(sorted("".join(sorted(input())), reverse=True))
print("Yes" if S < T else "No")
n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
a0 = a[0]
N = a0[0]
K = a0[1]
b = []
for i in range(K):
    di = a[2i+1]
    bi = a[2i+2]
for l in range(N):
    for i in range(K):
        for k in range(di):
            if not bi[k] == l:
            	b.append(l)
print(len(b))

### FIXED CODE ###

N, K = map(int, input().split())
d = []
A = []
s = [1] * N
for k in range(K):
  d.append(int(input()))
  A.append([int(i) for i in input().split()])
  
for k in range(K):
  for n in range(1, N+1):
    if n in A[k]:
      if s[n-1] == 1:
        s[n-1] = 0
print(sum(s))
n,k=map(int,input().split())
b=k
a=n-k
for i in range(1,k+1):
    if a+1<i:
        print("0")
        continue
    ans=1
    for j in range(i):
        ans*=a+1-j
        ans/=i-j
    for x in range(i-1):
        ans*=b-1-x
        ans/=i-1-x
    print(int(ans%1000000007))

### FIXED CODE ###

def ncr(n,r):
    if n==r: return 1
    if n<=0 or n<r:return 0
    r=min(r,n-r)
    a=1
    b=1
    for i in range(r):
        a*=n-i
        b*=r-i
    return a//b

n,k=map(int,input().split())
b=k
a=n-k
for i in range(1,k+1):
    print(int((ncr(a+1,i)*ncr(b-1,i-1))%1000000007))
import sys
sa = list(input())
sb = list(input())
sc = list(input())
sa = sa[::-1]
sb = sb[::-1]
sc = sc[::-1]
p = "a"
while True:
    if p == "a":
        p = sa.pop(-1)
        if len(sa) == 0 and p == "a":
            print("A")
            sys.exit()
    elif p == "b":
        p = sb.pop(-1)
        if len(sb) == 0 and p == "b":
            print("B")
            sys.exit()
    else:
        p = sc.pop(-1)
        if len(sc) == 0 and p == "c":
            print("C")
            sys.exit()
    

### FIXED CODE ###

import sys
sa = list(input())
sb = list(input())
sc = list(input())
sa = sa[::-1]
sb = sb[::-1]
sc = sc[::-1]
p = "a"
while True:
    if p == "a":
        if len(sa) > 0:
            p = sa.pop(-1)
        if len(sa) == 0 and p == "a":
            print("A")
            sys.exit()
    elif p == "b":
        if len(sb) > 0:
            p = sb.pop(-1)
        if len(sb) == 0 and p == "b":
            print("B")
            sys.exit()
    else:
        if len(sc) > 0:
            p = sc.pop(-1)
        if len(sc) == 0 and p == "c":
            print("C")
            sys.exit()
import bisect
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
	if s[i] == "R":
		r.append(i+1)
	elif s[i] == "G":
		g.append(i+1)
	else:
		b.append(i+1)
ans = 0
for i in r:
	for j in g:
		ans += len(b)
		if i > j:
			k = j-abs(i-j)
			m = i+abs(i-j)
		else:
			k = j+abs(i-j)
			m = i-abs(i-j)
		if k <= b[-1]:
			x = bisect.bisect_left(b,k)
			if b[x] == k:
				ans -= 1
		if m <= b[-1]:
			x = bisect.bisect_left(b,m)
			if b[x] == m:
				ans -= 1
		if i > j:
			k = i-abs(i-j)
		else:
			k = i+abs(i-j)
		if k in b:
			ans -= 1
		l = (i+j)//2
		if abs(i-l) == abs(j-l):
			x = bisect.bisect_left(b,l)
			if b[x] == l:
				ans -= 1
print (ans)

### FIXED CODE ###

import bisect
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
	if s[i] == "R":
		r.append(i+1)
	elif s[i] == "G":
		g.append(i+1)
	else:
		b.append(i+1)
ans = 0
if len(r) == 0 or len(g) == 0 or len(b) == 0:
	print (0)
	exit()
for i in r:
	for j in g:
		ans += len(b)
		if i > j:
			k = j-abs(i-j)
			m = i+abs(i-j)
		else:
			k = j+abs(i-j)
			m = i-abs(i-j)
		if k <= b[-1] and k >= b[0]:
			x = bisect.bisect_left(b,k)
			if x >= 0 and x < len(b):
				if b[x] == k:
					ans -= 1
		if m <= b[-1] and m >= b[0]:
			x = bisect.bisect_left(b,m)
			if x >= 0 and x < len(b):
				if b[x] == m:
					ans -= 1
		l = (i+j)//2
		if abs(i-l) == abs(j-l):
			x = bisect.bisect_left(b,l)
			if x >= 0 and x < len(b):
				if b[x] == l:
					ans -= 1
print (ans)
import math

n = int(input())
A = list(map(int, input().split()))
ans = 1e9
for i in range(1, n):
    ans = min(ans, math.gcd(A[i], A[i - 1]))
print(ans)

### FIXED CODE ###

def f(a, b):
    if a < b:
        d = a
        a = b
        b = d
    if a % b == 0:
        return b
    else:
        return f(b, a % b)

def main():
    n = int(input())
    A = list(map(int, input().split()))
    ans = int(1e9)
    for i in range(1, n):
        ans = min(ans, f(A[i], A[i - 1]))
    print(ans)

main()
import sys
from itertools import takewhile, dropwhile

L, pn, tmp = 224, [], [i for i in range(2, 50000)]
while tmp[0] < 224:
    v = tmp.pop(0)
    pn.append(v)
    tmp = list(filter(lambda x: x%v!=0, tmp))
for t in tmp: pn.append(t)

for line in sys.stdin:
    n = int(line.strip())
    print(list(takewhile(lambda x: x<n, pn))[-1], list(dropwhile(lambda x: x<n, pn))[1])

### FIXED CODE ###

primes = [0, 0] + [1]*50020
for i in range(2, 226):
    if primes[i]:
        for j in range(i*i, 50021, i):
            primes[j] = 0

while True:
    try:
        n = int(input())
    except:
        break
    print(n-primes[n-1::-1].index(1)-1, n+primes[n+1:].index(1)+1)
A, B, K = map(int, input().split())

nums = []
for num in range(A, min(A+K, B+1)):
  nums.append(num)
for num in range(min(B-K+1, a), B+1):
  if not num in nums:
    nums.append(num)
nums.sort()
for num in nums:
  print(num)

### FIXED CODE ###

A, B, K = map(int, input().split())

nums = []
for num in range(A, min(A+K, B+1)):
  nums.append(num)
for num in range(max(B-K+1, A), B+1):
  if not num in nums:
    nums.append(num)
nums.sort()
for num in nums:
  print(num)
import sys
N, M = map(int, input().split())

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    if n == 1:
        return 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

if M == 0:
    print(fib(N))

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)


new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

MOD = 1000000007


count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        #print(count)
print(count)

### FIXED CODE ###

import sys
N, M = map(int, input().split())

MOD = 1000000007

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    if n == 1:
        return 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

if M == 0:
    print(fib(N) % MOD)
    sys.exit()

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)


new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        #print(count)
print(count)
N = int(input())
H = list(map(int, input().split()))

best = 0
for i in range(N):
  for j in range(i+1,N):
    if H[i] < H[j]: break
  if j - i > best :
    best = j - i
print(best)

### FIXED CODE ###

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

best = []
a = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    a += 1
  else : 
    best.append(a)
    a = 0
best.append(a)
print(max(best))
import math
from functools import reduce

def gcd(numbers):
    return reduce(math.gcd, numbers)

city_num, ori = list(map(int, input().split()))
cityies = list(map(int, input().split()))
stan = cityies[0]
difference = [abs(ori-stan)]
print(difference)
print(gcd([2, 4, 6, 8]))

### FIXED CODE ###

import fractions
from functools import reduce

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

city_num, ori = list(map(int, input().split()))
cityies = list(map(int, input().split()))
stan = cityies[0]
difference = [abs(ori-stan)]

if len(cityies) > 1:
    for city in cityies[1:]:
        diff = abs(city - stan)
        difference.append(diff)

max_num = gcd(difference)
print(max_num)
n,k= map(int, input().split())
a= list(map(int, input().split()))
a.sort()

if k==0:
    print(a[-1])
    exit()


# めぐる式二部探索
l=-1
r=pow(10,11)
while r-l>1:
    # rは常にOK、lは常にNG。
    mid=l+(r-l)//2
    cnt=k
    flag=True
    for i in range(n):
        if a[i]>mid:
            cnt-=a[i]//mid

    # なんらかの判定
    if cnt>=0:
        r = mid  # 判定がOKのとき→範囲を左に狭める
    else:
        l = mid  # 判定がNGのとき→範囲を右に狭める

print(r)

### FIXED CODE ###

n,k= map(int, input().split())
a= list(map(int, input().split()))
a.sort()

if k==0:
    print(a[-1])
    exit()


# めぐる式二部探索
l=0
r=pow(10,11)
while r-l>1:
    # rは常にOK、lは常にNG。
    mid=l+(r-l)//2
    cnt=k
    flag=True
    for i in range(n):
        if a[i]>mid:
            x=-(-a[i]//mid)-1
            cnt-=x

    # なんらかの判定
    if cnt>=0:
        r = mid  # 判定がOKのとき→範囲を左に狭める
    else:
        l = mid  # 判定がNGのとき→範囲を右に狭める

print(r)
import fractions
def mygcd(N,A,S):
    if S == 'R':
        A.reverse()
    ans = [0, A[0]]
    for i in range(1, N):
        ans.append(fractions.gcd(ans[i],A[i]))
    if S == 'R':
        ans.reverse()
    return ans

def GCDonBlack(N,A):
    L = mygcd(N,A,'L')
    R = mygcd(N,A,'R')
    M = [fractions.gcd(L[i], R[i+1])  for i  in range(0,N)]
    return max(M)

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

### FIXED CODE ###

A,B,T = map(int, input().split())
ans = round((T+0.5)//A)*B
print(ans)
import math,sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
MOD = 1000000007
d = defaultdict(int)
for i in range(n):
  a,b = map(int,input().split())
  g = math.gcd(a,b)
  a,b = a//g,b//g
  if a<0:
    a,b = -a,-b
  d[str(a)+':'+str(b)] += 1
c = 1
for i in d.keys():
  if d[i] != 0:
    cur = pow(2,d[i],MOD)
    if '-' in i:
      ind = i.index(':')
      ci = i[ind+2:] + ':' + i[:ind]
    else:
      ind = i.index(':')
      ci = i[ind+1:] + ':-' + i[:ind]
    if ci in d.keys():
      cur += pow(2,d[ci],MOD)-1
      d[ci] = 0
    c = (c*cur)%MOD
print(c-1)

### FIXED CODE ###

import math,sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
MOD = 1000000007
d = defaultdict(int)
l,r = 0,0
count = 0
for i in range(n):
  a,b = map(int,input().split())
  if a == b == 0:
    count += 1
    continue
  elif a == 0 or b == 0:
    if a == 0:
      l += 1
    else:
      r += 1
  else:
    g = math.gcd(a,b)
    a,b = a//g,b//g
    if a<0:
      a,b = -a,-b
    d[str(a)+':'+str(b)] += 1
c = 1
for i in d.keys():
  if d[i] != 0:
    cur = pow(2,d[i],MOD)
    if '-' in i:
      ind = i.index(':')
      ci = i[ind+2:] + ':' + i[:ind]
    else:
      ind = i.index(':')
      ci = i[ind+1:] + ':-' + i[:ind]
    if ci in d.keys():
      cur += pow(2,d[ci],MOD)-1
      d[ci] = 0
    c = (c*cur)%MOD
c = (c*(pow(2,l,MOD)+pow(2,r,MOD)-1)-1+count)%MOD
print(c)
N = input()
d = [input() for i in range(int(N))]
print(len(set(d))

### FIXED CODE ###

N = input()
d = [input() for i in range(int(N))]
print(len(set(d)))
H = int(input())
total = 1
while H > 1:
  H = H // 2
  if H != 0:
    total += 1
number = 0
for i in range(tatal):
  number += 2 ** i
print(number)


### FIXED CODE ###

H = int(input())
def re(a):
  if a == 1:
    return 1
  return 2 * re(a//2) + 1
print(re(H))
h, w = map(int, input().split())
hw = [input() for _ in range(h)]
dp = [[1000]*w for _ in range(h)]
if hw[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(w):
    for j in range(h):
        if i > 0:
            if hw[i][j] == "#" and hw[i-1][j] == ".":
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
            else:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
        if j > 0:
            if hw[i][j] == "#" and hw[i][j-1] == ".":
                dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
            else:
                dp[i][j] = min(dp[i][j], dp[i][j-1])

print(dp[h-1][w-1])

### FIXED CODE ###

h, w = map(int, input().split())
hw = [input() for _ in range(h)]
dp = [[1000]*w for _ in range(h)]
if hw[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(h):
    for j in range(w):
        if i > 0:
            if hw[i][j] == "#" and hw[i-1][j] == ".":
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
            else:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
        if j > 0:
            if hw[i][j] == "#" and hw[i][j-1] == ".":
                dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
            else:
                dp[i][j] = min(dp[i][j], dp[i][j-1])

print(dp[h-1][w-1])
n = int(input())
l = list(map(int,input().split()))

def ans(x,L):
    ans = 1
    flag = 0
    tmp = L[0:2]
    if tmp[0] < tmp[1]:
        flag  = 1
    elif tmp[0] > tmp[1]:
        flag = -1
    for i in range(2,n):
        tmp.append(L[i])
        if len(tmp) == 1 and i == n-1:
            pass
        elif (flag == -1 and tmp[-2] < tmp[-1]) or (flag == 1 and tmp[-2] > tmp[-1]):
            ans += 1
            flag = 0
            tmp = [tmp[-1]]
        elif flag == 0 and tmp[-2] < tmp[-1]:
            flag = 1
        elif flag == 0 and tmp[-2] > tmp[-1]:
            flag = -1
    return(ans)
print(ans(n,l))  

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))

def ans(x,L):
    ans = 1
    flag = 0
    tmp = L[0:2]
    if tmp[0] < tmp[1]:
        flag  = 1
    elif tmp[0] > tmp[1]:
        flag = -1
    for i in range(2,n):
        tmp.append(L[i])
        if len(tmp) == 1:
            pass
        elif (flag == -1 and tmp[-2] < tmp[-1]) or (flag == 1 and tmp[-2] > tmp[-1]):
            ans += 1
            flag = 0
            tmp = [tmp[-1]]
        elif flag == 0 and tmp[-2] < tmp[-1]:
            flag = 1
        elif flag == 0 and tmp[-2] > tmp[-1]:
            flag = -1
    return(ans)
if n <= 2:
    print(1)
else:
    print(ans(n,l))
w, h, x, y = map(int, input().split())

s = w * h / 2
if (x * 2 == w) and (y * 2 == h):
    print(s, 1)
else:
    print(s, 0)

### FIXED CODE ###

x, a = map(int, input().split())

if x < a:
    print(0)
else:
    print(10)
A = input()
a,b = (A.split' ')
c = int(a)
d = int(b)
if 0 < c < 11:
   print('d')
else:
   print('d+1000-100c')

### FIXED CODE ###

A = input()
b,c = (A.split(' '))
d = int(b)
e = int(c)
f = e - d * 100 + 1000

if 0 < d < 11:
    print(f)
else:
    print(e)
s = raw_input()
max0, max1 = -1, -1
cnt = 0
t = ""
for i in range(len(s)):
    if i == 0:
        t += s[i]
    
    elif s[i] == "0" and s[i-1] == "0":
        t += s[i]
    elif s[i] == "0" and s[i-1] == "1":
        max1 = max(max1, len(t))
        t = "0"
        cnt += 1
    elif s[i] == "1" and s[i-1] == "1":
        t += s[i]
    elif s[i] == "1" and s[i-1] == "0":
        max0 = max(max0, len(t))
        t = "1"
        cnt += 1

if t.count("0") == 0:
    max1 = max(max1, len(t))
else:
    max0 = max(max0, len(t))

if s.count("0") == len(s) or s.count("1") == len(s):
    print "0"
elif len(s) == 2:
    print "1"
elif cnt == 1:
    print max(max(max1, max0), 2)
else:
    print max(max1 + max0)


### FIXED CODE ###

s = raw_input()

n = ans = len(s)

for i in range(len(s) - 1):
    if s[i] != s[i+1]:
        ans = min(ans, max(i + 1, n - (i + 1)))

print ans
MOD = 10**9+7
N = int(input())
L = list(map(lambda x: bin(int(x))[2:], input().split()))
max_len = max([len(v) for v in L])
padL = ["0"*(max_len-len(v))+v for v in L]
cnt = [0]*max_len
for i in range(max_len):
    for l in padL:
        cnt[i] += 1 if l[i] == "1" else 0

ans = 0
v = 1
for i in range(max_len):
    ans += v*cnt[max_len-1-i]*(N-cnt[max_len-i-1])
    ans %= MOD
    v *= 2

print(ans)


### FIXED CODE ###

M = 3501
N = int(input())
for h in range(1, M):
    for w in range(1, M):
        u = 4*h*w-N*w-N*h
        d = N*h*w
        if u <= 0:
            continue
        if d % u == 0:
            print(h, w, d//u)
            exit()
n,m,x,y = map(int,input().split())
X = map(int,input().split())
Y = map(int,input().split())
if max(X)+1 <= min(Y) and max(X) > x and min(Y) <= y:
    print("No War")
else:
    print("War")

### FIXED CODE ###

n,m,x,y = map(int,input().split())
X = list(map(int,input().split()))
Y = list(map(int,input().split()))
if max(X)+1 <= min(Y) and max(X) > x and min(Y) <= y:
    print("No War")
else:
    print("War")
a,b = map(int,input().split())

if a % 3 == 0 or b % 3 == 0 or (a + b) % 3 == 0
	print("Possible")
else:
  	print("Impossible")

### FIXED CODE ###

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

if a % 3 == 0 or b % 3 == 0 or (a + b) % 3 == 0:
	print("Possible")
else:
  	print("Impossible")
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key,lru_cache
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
# import sys
# input = sys.stdin.readline
 
M = mod = 10**9 + 7 
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip().split()]
def st():return str(input().rstrip())[2:-1]
def val():return int(input().rstrip())
def li2():return [str(i)[2:-1] for i in input().rstrip().split()]
def li3():return [int(i) for i in st()]
 



sys.setrecursionlimit(10 ** 5 + 10)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1

    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = defaultdict(set)

for _ in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)


root = 1
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

### FIXED CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
 



sys.setrecursionlimit(10 ** 6)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = [[] for i in range(n + 1)]

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].append(b)
    g[b].append(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)
Sp = [1,2,3,4,5,6,7,8,9,10,11,12,13]
Hu = [1,2,3,4,5,6,7,8,9,10,11,12,13]
Cr = [1,2,3,4,5,6,7,8,9,10,11,12,13]
Dy = [1,2,3,4,5,6,7,8,9,10,11,12,13]

num = input()
i = 0
while i < num:
     suit, n = raw_input().split
     n = int(n)
     if suit == "S":
        Sp[n-1] = 0
     elif suit == "H":
        Hu[n-1] = 0
     elif suit == "C":
        Cr[n-1] = 0
     else:
        Dy[n-1] = 0
     i += 1

for i in Sp:
    if i != 0:
        print "S", i

for i in Hu:
    if i != 0:
        print "H", i

for i in Cr:
    if i != 0:
        print "C", i

for i in Dy:
    if i != 0:
        print "D", i

### FIXED CODE ###

Sp = [1,2,3,4,5,6,7,8,9,10,11,12,13]
Hu = [1,2,3,4,5,6,7,8,9,10,11,12,13]
Cr = [1,2,3,4,5,6,7,8,9,10,11,12,13]
Dy = [1,2,3,4,5,6,7,8,9,10,11,12,13]

num = int(input())
i = 0

while i < num:
     suit, n = raw_input().split()
     n = int(n)
     if suit == "S":
        Sp[n-1] = 0
     elif suit == "H":
        Hu[n-1] = 0
     elif suit == "C":
        Cr[n-1] = 0
     else:
        Dy[n-1] = 0
     i += 1

for i in Sp:
    if i != 0:
        print "S", i

for i in Hu:
    if i != 0:
        print "H", i

for i in Cr:
    if i != 0:
        print "C", i

for i in Dy:
    if i != 0:
        print "D", i
# -*- coding: utf-8 -*-
N = int(input())
if N > 3:
  print("{}".format(int(N // 3) + 1)
elif N <= 3:
        print(0)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
if N <= 2:
  print(0)
else:
  print(int(N // 3))
import numpy as np
a = input()
n, l= a.split(" ")
apples = [i for i in range(n)]
abs_app = np.abs(apples)
m = abs_app.min()
print((np.array(apples)[abs_app == m]).sum())


### FIXED CODE ###

import numpy as np
a = input()
n, l = [int(i) for i in a.split(" ")]
apples = np.array([i for i in range(n)])
aji = apples + l
abss = [np.abs(aji[apples != i].sum() - aji.sum()) for i in range(n)]
i = abss.index(np.min(abss))
print(aji[apples != i].sum())