Harryxun/stf_run huggingface dataset:
from collections import Counter

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

# print('*')

keys = list(cities.keys())

for l in range(len(keys)):
    for i in range(len(keys)):
        for j in range(len(keys)):
            k = keys[l]
            a = keys[a]
            b = keys[b]

            c = costs[a][k] + costs[k][b]
            if a != b and costs[a][b] > c:
                costs[a][b] = c

# print('*')

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = 100000 + 1

def f(selected, rest):
    global smallest
    if len(rest) == 0:
        c = cost(selected)
        if smallest > c:
            smallest = c
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            if len(selected) == 1 or cost(selected + [r]) < smallest:
                f(selected + [r], rest_copy)

f([], rs)
print(smallest)


### FIXED CODE ###

from itertools import permutations

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

costs = {}
for i in range(n + 1):
    costs[i] = {}
    for j in range(n + 1):
        costs[i][j] = float('inf')

for _ in range(m):
    a, b, c = read_line(int, int, int)

    costs[a][b] = costs[b][a] = c

for k in range(n + 1):
    for i in range(n + 1):
        for j in range(n + 1):
            c = costs[i][k] + costs[k][j]
            if costs[i][j] > c:
                costs[i][j] = c

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = float('inf')

for p in permutations(rs):
    c = cost(p)
    if smallest > c:
        smallest = c

print(smallest)
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
al=[int(input()) for i in range(m)]
mod=1000000007
ms=[0]*n

def dd(n):
    if ms[n-1]>0:
        return ms[n-1]
    if n==1:
        ms[n-1]=1
        return 1
    if n==2:
        ms[n-1]=2
        return 2
    m=dd(n-1)+dd(n-2)
    ms[n-1]=m
    return m

ans=1
now=0
b=-1
for a in al:
    if a-1==b:
        print(0)
        exit()
    b=a
    if a-1!=now:
        ans=(ans%mod)*(dd(a-now-1)%mod)%mod
    now=a+1

if m!=0:
    ans=(ans%mod)*(dd(n-al[-1]-1)%mod)%mod
else:
    ans=dd(n)%mod
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
al=[int(input()) for i in range(m)]+[n+1]
mod=1000000007
ms=[0]*(n+1)

def dd(n):
    if ms[n]>0:
        return ms[n]
    if n==1:
        ms[n]=1
        return 1
    if n==2:
        ms[n]=2
        return 2
    m=dd(n-1)+dd(n-2)
    ms[n]=m
    return m

ans=1
now=0
b=-1
for a in al:
    if a-1==b:
        print(0)
        exit()
    b=a
    if a-1!=now:
        ans=(ans%mod)*(dd(a-now-1)%mod)%mod
    now=a+1

print(ans)
n=int(input())
p=list(map(int,input().split()))
ct=1
i=1
maxn=p.index(i)
while True:
    p=p[0:maxn]
    i+=1
    maxn=p.index(min(p))
    ct+=1
    if maxn==0:
        break
print(ct)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
ct=1
minn=p[0]
for i in range(1,n):
    if minn==1:
        #ct+=1
        break
    elif minn>p[i]:
        minn=p[i]
        ct+=1
print(ct)
import sympy
n=int(input())
a=0
for i in range(1,n+1):
  
  a+=sympy.divisor_count(i)
print(a)

### FIXED CODE ###

n=int(input())
ass=0
for j in range(1,n+1):
  ass+=int(n/j)*(int(n/j)+1)*j//2
  
print(ass)
a = map(int, input().split())
if a.sort() == [5,5,7]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a = list(map(int, input().split()))
a.sort()
if a == [5,5,7]:
    print('YES')
else:
    print('NO')
k,s = map(int,input().split())

count = 0
num = range(k+1)
for x in num:
  for y in num:
    if x + Y > s:
      break
    for z in num:
      if x + y + z == s:
        count += 1
      elif x + y + z > s:
        break

print(count)

### FIXED CODE ###

k,s = map(int,input().split())

count = 0
for x in range(k+1):
  for y in range(k+1):
    a = s - x - y
    if a >= 0 and a <= k:
      count += 1

print(count)
N = int(input())
A = [int(hoge) for hoge in input().split()]
A = list(range(2,1000001))
A.sort()
M = max(A)
dp = [False] * (M+ 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (M// a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)

### FIXED CODE ###

X,N = [int(hoge) for hoge in input().split()]
P = [int(hoge) - X for hoge in input().split()]
for d in range(101):
    if (d in P) and (-d in P):
        continue
    elif -d in P:
        print(X + d)
        exit()
    else:
        print(X - d)
        exit()
N, Q = map(int, input().split())
S = input()
t = []*(N+1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0]*(N+1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
import sys

for line in sys.stdin:
    A=line.split()
    B=map(int,A)

D=B.sort()
e=1

while e != 0:
    e=D[1]%D[0]
    C=[0]
    D[0]=e
    D[1]=C

print D[0]

### FIXED CODE ###

A=map(int,raw_input().split())
A.sort()

while A[1]%A[0]!=0:
    temp=A[0]
    A[0]=A[1]%A[0]
    A[1]=temp

print A[0]
from collections import deque
n = int(input())
an = list(map(int, input().split()))

an.sort()
an = deque(an)
ls = deque()
same = -1
while an:
    a = an.popleft()
    t = True
    if same == a:
      continue
    for i in ls:
        if a == i:
            ls.pop()
            same = a
            t = False
            break
        if a % i == 0:
            t = False
            break
    if t:
        ls.append(a)

print(len(ls))


### FIXED CODE ###

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

for i in range(5):
    if x[i] == 0:
        print(i + 1)
        exit()
FC = '#'
PC = '.'

def bothends(f):
    def _func(self):
        print(FC, end='')
        f(self)
        print(FC)
    return _func

class Frame:
    c = FC
    s = PC
    def __init__(self, w, h):
        self.w = w
        self.h = h
        
    @bothends
    def _draw(self):
        print(self.s * (self.w - 2), end='')

    def draw(self):
        for i in range(self.h - 2):
            self._draw()

    def __enter__(self):
        print(self.c * self.w)
        return self

    def __exit__(self, exc_type, exc_value, traceback):
        print(self.c * self.w)
        return True

while True:
    w, h = [ int(s) for s in input().split() ]
    if w == h == 0:
        break
    with Frame(w, h) as fr:
        fr.draw()
    print()

### FIXED CODE ###

from __future__ import print_function

FC = '#'
PC = '.'

def bothends(f):
    def _func(self):
        print(FC, end='')
        f(self)
        print(FC)
    return _func

class Frame:
    c = FC
    s = PC
    def __init__(self, w, h):
        self.w = w
        self.h = h
        
    @bothends
    def _draw(self):
        print(self.s * (self.w - 2), end='')

    def draw(self):
        for i in range(self.h - 2):
            self._draw()

    def __enter__(self):
        print(self.c * self.w)
        return self

    def __exit__(self, exc_type, exc_value, traceback):
        print(self.c * self.w)
        return True

while True:
    w, h = [ int(s) for s in raw_input().split() ]
    if w == h == 0:
        break
    with Frame(h, w) as fr:
        fr.draw()
    print()
S = input()
T = input()

N = len(S)
M = len(T)

if N < M:
    print('UNRESTORABLE')
    
else:

    ans = 'UNRESTORABLE'
    for i in range(N-M+1):
        make = True
        for j in range(M):
            if S[i+j] != '?' and S[i+j] != T[j]:
                make = 0
        if make:
            ans = S[:i] + T + S[i+M:]
    ans = list(ans)
    for i in range(N):
        if ans[i] == '?':
            ans[i] = 'a'
    print(''.join(ans))


### FIXED CODE ###

S = list(input())
T = list(input())
lenS = len(S)
lenT = len(T)
change = 0
for i in range(lenS-lenT,-1,-1):
    a = 1
    for j in range(lenT):
        if S[i+j] != T[j] and S[i+j] != '?':
            a = 0
    if a == 1:
        for j in range(lenT):
            S[i+j] = T[j]
        change = 1
        break

for i in range(lenS):
    if S[i] == '?':
        S[i] = 'a'

if change == 1:
    print(''.join(S))
else:
    print('UNRESTORABLE')
from sys import stdin

n = int(input())
r = int(input())

if n < 11:
    a = r - 100 * (10-n)
else:
    a = r

print(n)


### FIXED CODE ###

from sys import stdin

n,r=map(int,input().split())

if n < 10:
    print(r + 100 * (10-n))
else:
    print(r)
n, k = map(int, input().split())
l = list(map(int, input().split()))
m = max(l)
def hcf(x, y): 
    while(y): 
        x, y = y, x % y 
    return x 
num1=l[0] 
num2=l[1] 
gcd=hcf(num1,num2) 
for i in range(2,len(l)): 
    gcd=hcf(gcd,l[i])
if k%gcd == 0 and k<=m:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

import math
from functools import reduce
n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
def hcf(l):
    return reduce(math.gcd, l)
gcd = hcf(A)
m = max(A)
if k%gcd == 0 and k<=m:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
N = int(input())

if N % 2 == 0:
  print(N)
else:
  print(2N)

### FIXED CODE ###

N = int(input())
 
if N % 2 == 0:
  print(N)
else:
  print(2 * N)
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  h, w, m = map(int, input().strip().split())
  fieldh = numpy.zeros(h, dtype=numpy.int)
  fieldw = numpy.zeros(w, dtype=numpy.int)
  field = numpy.zeros((h, w), dtype=numpy.int)
  for _ in range(m):
    ih, iw = map(int, input().strip().split())
    fieldh[ih-1] += 1
    fieldw[iw-1] += 1
    field[ih-1, iw-1] = 1
    
  max_h = numpy.max(fieldh)
  max_w = numpy.max(fieldw)
  argsort_h = [ ih for ih in range(h) if fieldh[ih] == max_h ]
  argsort_w = [ iw for iw in range(w) if fieldw[iw] == max_w ]
  
  max_cnt = 0
  for ih in argsort_h:
    for iw in argsort_w:
      if field[ih, iw] == 0:
        max_cnt = max(max_cnt, fieldh[ih]+fieldw[iw])
        print(max_cnt)
        return 
      else:
        max_cnt = max(max_cnt, fieldh[ih]+fieldw[iw]-1)
  print(max_cnt)

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from collections import defaultdict

def main():
  h, w, m = map(int, input().strip().split())
  fieldh = numpy.zeros(h, dtype=numpy.int)
  fieldw = numpy.zeros(w, dtype=numpy.int)
  field = defaultdict(int)
  for _ in range(m):
    ih, iw = map(int, input().strip().split())
    fieldh[ih-1] += 1
    fieldw[iw-1] += 1
    field[ih-1, iw-1] = 1
    
  max_h = numpy.max(fieldh)
  max_w = numpy.max(fieldw)
  argsort_h = [ ih for ih in range(h) if fieldh[ih] == max_h ]
  argsort_w = [ iw for iw in range(w) if fieldw[iw] == max_w ]
  
  max_cnt = 0
  for ih in argsort_h:
    for iw in argsort_w:
      if field[ih, iw] == 0:
        max_cnt = max(max_cnt, fieldh[ih]+fieldw[iw])
        print(max_cnt)
        return 
      else:
        max_cnt = max(max_cnt, fieldh[ih]+fieldw[iw]-1)
  print(max_cnt)

if __name__=='__main__':
  main()
import sys
sys.setrecursionlimit(10000)
def make_tree(node):
    for i in tree_list[node]:
        if i != tree_dic[node]["p"]:
            tree_dic[node]["c"].append(i)
            tree_dic[i]["p"] = node
            make_tree(i)

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

tree_dic = {} #tree_dic = {i:{p:j, c:[k, l]}}
for i in range(n):
    tree_dic[i] = {"p": None, "c": [], "x": 0}

make_tree(0)

for i in range(q):
    p, x = map(int, input().split())
    tree_dic[p-1]["x"] += x
# print(tree_dic)

x_list = [0 for _ in range(n)]

import queue
next_visit = queue.Queue()
next_visit.put(0)
while not next_visit.empty():
    i = next_visit.get()
    tmp = tree_dic[i]["x"]
    if i != 0:
        tmp += x_list[tree_dic[i]["p"]]
    x_list[i] = tmp
    for j in tree_dic[i]["c"]:
        next_visit.put(j)

for i in x_list:
    print(i, end=" ")

### FIXED CODE ###

n, q = map(int, input().split())
tree_candidate = [[] for _ in range(n)]

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

tree = [[] for _ in range(n)]

app = set([0])

import queue
next = queue.Queue()
next.put(0)
# print(tree_candidate)
while not next.empty():
    i = next.get()
    for j in tree_candidate[i]:
        if not j in app:
            tree[i].append(j)
            app.add(j)
            next.put(j)

cnts = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    cnts[p-1] += x
    # print(x, p, tree[p-1], cnts)

next = queue.Queue()
next.put(0)

while not next.empty():
    i = next.get()
    for j in tree[i]:
        cnts[j] += cnts[i]
        next.put(j)

for i in cnts:
    print(i, end=' ')
x,a=map(int,input().split())
b=0
c=0
A=[int(input()) for _ in range(x)]
while b<=a:
    b=b+A[c]
    c+=1
print(c)

### FIXED CODE ###

a,b=map(int,input().split())
l=list(map(int,input().split()))
c=1
d=0
r=len(l)
for i in range(r):
    d=d+l[i]
    if d<=b:
        c=c+1
 
        
print(c)
import numpy as np
N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))

kernel = [1] * K
est = (p + 1) / 2

est_k = np.convolve(est, kernel)
print(np.max(est_k))

### FIXED CODE ###

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

p.insert(0, 0)
for i in range(1, N+1):
    p[i] = (p[i] + 1) / 2 + p[i-1]

s = [0] * (N+1)
for i in range(N-K+1):
    s[i] = p[i+K] - p[i]

print(max(s))
import collections


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

if len(set(l)) == 1:
    print(n//2)
    exit()

leven = [x for x in l[::2]]
lodd  = [x for x in l[1::2]]

ce = collections.Counter(leven)
co = collections.Counter(lodd)
ce = sorted(ce.items(), key=lambda x:x[1])
co = sorted(co.items(), key=lambda x:x[1])

if ce[-1][0] != ce[-1][0]:
	print(n - ce[-1][1] - co[-1][1])
elif ce[-2][1] > co[-2][1]:
    print(n - ce[-2][1] - co[-1][1])
else:
    print(n - ce[-1][1] - co[-2][1])


### FIXED CODE ###

import collections


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

if len(set(l)) == 1:
    print(n//2)
    exit()

leven = [x for x in l[::2]]
lodd  = [x for x in l[1::2]]

ce = collections.Counter(leven)
co = collections.Counter(lodd)
ce = sorted(ce.items(), key=lambda x:x[1])
co = sorted(co.items(), key=lambda x:x[1])

if ce[-1][0] != co[-1][0]:
	print(n - ce[-1][1] - co[-1][1])
elif ce[-2][1] > co[-2][1]:
    print(n - ce[-2][1] - co[-1][1])
else:
    print(n - ce[-1][1] - co[-2][1])
n,m=map(int,input().split())
M=[]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    M.append([a,b])
yes="POSSIBLE";no="IMPOSSIBLE"

for i in M[0]:
    if n-1 in M[i]:
        print(yes);exit()
print(no)



### FIXED CODE ###

n,m=map(int,input().split())
M=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    M[a].append(b)
    M[b].append(a)
yes="POSSIBLE";no="IMPOSSIBLE"

for i in M[0]:
    if n-1 in M[i]:
        print(yes);exit()
print(no)
N,K,L = map(int, input().split())


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank 
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
PQ = [ [int(j) for j in input().split()] for _ in range(K)]
RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = PQ[i]
    UF1.unite(p,q)
for i in range(L):
    p,q = RS[i]
    UF2.unite(p, q)
counter=[]
from collections import defaultdict
cntdic =defaultdict(int)
for i in range(1,N+1):
  counter.append(UF1.find(i)+UF2.find(i)*10**6)
  cntdic[counter[-1]]+=1 

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = cntdic[counter[i]]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))


### FIXED CODE ###

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank 
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
# MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
#PQ = [ [int(j) for j in input().split()] for _ in range(K)]
#RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = map(int,input().split())
    UF1.unite(p,q)
for i in range(L):
    p,q = map(int,input().split())#RS[i]
    UF2.unite(p, q)
counter=[]
from collections import defaultdict
cntdic =defaultdict(int)
for i in range(1,N+1):
  counter.append(UF1.find(i)+UF2.find(i)*10**6)
  cntdic[counter[-1]]+=1 

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = cntdic[counter[i-1]]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))
# -*- coding: utf-8 -*-

def qui(l):
    num = len(l)
    if num <= 1: return l
    piv = 0
    piv2 = len(l)-1
    piv3 = int(len(l)/2)
    if l[piv] > l[piv2] > l[piv3]:
        piv = piv2
    elif l[piv] > l[piv3] > l[piv2]:
        piv = piv3
    mini = []
    maxi = []

    for i in range(0,len(l)):
        if i == piv:
            continue
        if l[piv] > l[i]:
            mini.append(l[i])
        elif l[piv] <= l[i]:
            maxi.append(l[i])
    return qui(mini) + [l[piv]] + qui(maxi)

input()
list1 = list(map(lambda x: int(x), input().split(" ")))
result = qui(list1)

print(' '.join(map(str, result)))

### FIXED CODE ###

# -*- coding: utf-8 -*-

import random
def qui(l):
    num = len(l)
    if num <= 1:
        return l
    piv = random.randrange(0,len(l))
    piv2 = random.randrange(0,len(l))
    piv3 = random.randrange(0,len(l))
    if (l[piv] > l[piv2]) and (l[piv2] > l[piv3]):
        piv = piv2
    elif (l[piv] > l[piv3]) and (l[piv3] > l[piv2]):
        piv = piv3
    elif (l[piv] < l[piv2]) and (l[piv2] < l[piv3]):
        piv = piv2
    elif (l[piv] < l[piv3]) and (l[piv3] < l[piv2]):
        piv = piv3
    else:
        pass
    mini = []
    middlei = []
    maxi = []

    for i in range(0,len(l)):
        if l[i] == l[piv]:
            middlei.append(l[i])
        elif l[piv] > l[i]:
            mini.append(l[i])
        elif l[piv] <= l[i]:
            maxi.append(l[i])
    mini = qui(mini)
    maxi = qui(maxi)
    return mini+ middlei+maxi
input()
list1 = input().split(" ")
for i in range(0, len(list1)):
    list1[i] = int(list1[i])

result = qui(list1)

print(' '.join(map(str, result)))
n=int(input())
adj=[[] for i in range(n+1)]
dp=[[-1,-1] for i in range(n+1)]
mod=10**9 +7
def dfs(node,parent,color):
    if dp[node][color]!=-1:
        return dp[node][color]
    count=1
    if color==0:
        for i in adj[node]:
            if i==parent:
                continue
            temp=(dfs(i,node,0)+dfs(i,node,1))%mod
            count=(count*temp)%mod
    else:
        for i in adj[node]:
            if i==parent:
                continue
            temp=dfs(i,node,0)%mod
            count=(count*temp)%mod
    dp[node][color]=count
    return count
for _ in range(n-1):
    u,v=map(int,input().split())
    adj[u].append(v)
    adj[v].append(u)
print((dfs(1,-1,0)+dfs(1,-1,1))%mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n=int(input())
adj=[[] for i in range(n+1)]
dp=[[-1,-1] for i in range(n+1)]
mod=10**9 +7
def dfs(node,parent,color):
    if dp[node][color]!=-1:
        return dp[node][color]
    count=1
    if color==0:
        for i in adj[node]:
            if i==parent:
                continue
            temp=(dfs(i,node,0)+dfs(i,node,1))%mod
            count=(count*temp)%mod
    else:
        for i in adj[node]:
            if i==parent:
                continue
            temp=dfs(i,node,0)%mod
            count=(count*temp)%mod
    dp[node][color]=count
    return count
for _ in range(n-1):
    u,v=map(int,input().split())
    adj[u].append(v)
    adj[v].append(u)
print((dfs(1,-1,0)+dfs(1,-1,1))%mod)
N, K = map(int, input().split())

h = list(map(int(input().split())))

ans = 0
for i in h:
    if i>=K:
        ans+=1

print(ans)

### FIXED CODE ###

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

h = list(map(int,(input().split())))

ans = 0
for i in h:
    if i>=K:
        ans+=1


print(ans)
from collections import deque

n = int(input())

result = deque()
index = 0

if n % 2 == 0
    for i in input().split():
        if index % 2 == 1:
            result.appendleft(i)
            index += 1
        else:
            result.append(i)
            index += 1
else:
    for i in input().split():
        if index % 2 == 1:
            result.append(i)
            index += 1
        else:
            result.appendleft(i)
            index += 1

print(" ".join(result))

### FIXED CODE ###

from collections import deque

n = int(input())

result = deque()
index = 0

if n % 2 == 0:
    for i in input().split():
        if index % 2 == 1:
            result.appendleft(i)
            index += 1
        else:
            result.append(i)
            index += 1
else:
    for i in input().split():
        if index % 2 == 1:
            result.append(i)
            index += 1
        else:
            result.appendleft(i)
            index += 1

print(" ".join(result))
import math

R = int(input())

pai = math.pi

print(2 * R * pi)

### FIXED CODE ###

import math

R = int(input())

pai = math.pi

print(2 * R * pai)
a,b=map(int,split())
if a*b%2=0:
  print('Even')
else:
  print('Odd')

### FIXED CODE ###

a, b = map(int, input().split())
if a * b % 2 == 0:
  print('Even')
else:
  print('Odd')
a=int(input())
b=int(input())
c=(a-1)
d=(b-1)
print(c*d)

### FIXED CODE ###

a,b=map(int,input().split())
print((a-1)*(b-1))