Harryxun/stf_run huggingface dataset:
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
b=[0]*(m-1)
for i in range(0,m-1):
  b[i]=a[i+1]-a[i]
c=sorted(b)
s=a[m-1]-a[0]
for i in range(0,n-1):
  s=s-c[m-i-2]
print(s)

### FIXED CODE ###

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
b=[0]*(m-1)
for i in range(0,m-1):
  b[i]=a[i+1]-a[i]
c=sorted(b)
s=a[m-1]-a[0]
if m>n:
  for i in range(0,n-1):
  	s=s-c[m-i-2]
else:
  s=0
print(s)
h = int(input())
mount = [int(_) for _ in input().split()]
count = 0
for i in range(h):
  if i = 0:
    count += 1
  else:
    if mount[i]>mount[i-1]:
      count += 1
print (count)

### FIXED CODE ###

h = int(input())
mount = [int(_) for _ in input().split()]
count = 0
for i in range(h):
  if i == 0:
    count += 1
  else:
    for j in range(i):
      if mount[i]<mount[j]:
        break
    else:
      count += 1
print (count)
n, k = list(map(int, input().split()))

proba = 0
for i in range(1, N+1):
  x = i
  p = 1
  while x < K:
    p *= 0.5
    x += 1
  proba += p/N
  


### FIXED CODE ###

N, K = list(map(int, input().split()))
 
ans = 0
for i in range(1, N+1):
    p = 1
    x = i
    while x < K:
        p *= 0.5
        x *= 2
    
    ans += p/N
 
print(ans)
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

nc = raw_input()
nc = nc.split()
n,c = map(int,nc)

tt = np.zeros([(10**2),c],int)

for i in range(n):
    stc = raw_input()
    stc = stc.split()
    s,t,c = map(int,stc)
    j = s
    while j <= t:
        tt[j-1][c-1] = 1
        j += 1

ans = np.max(np.sum(tt, axis=1))

print ans


### FIXED CODE ###

#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

nc = raw_input()
nc = nc.split()
n,c = map(int,nc)

tt = np.zeros([(10**5),c],int)

for i in range(n):
    stc = raw_input()
    stc = stc.split()
    s,t,c = map(int,stc)
    j = s
    while j <= t:
        tt[j-1][c-1] = 1
        j += 1

ans = np.max(np.sum(tt, axis=1))

print ans
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

ans = [0] * (10**9)
for i in range(N):
    if ans[i] == 0:
        ans[i] = 1
    if ans[i] == 1:
        ans[i] = 0

print(sum(ans[i]))

### FIXED CODE ###

N = int(input())

A = []
for _ in range(N):
    A.append(int(input()))

if N == 1:
    print(1)
    exit()

A.sort()

current_number = A[0]
current_count = 1
ans = 0

for i in range(1,N-1):
    if current_number == A[i]:
        current_count += 1
    else:
        current_number = A[i]
        if current_count % 2 != 0:
            ans += 1
        current_count = 1

if current_number == A[N-1]:
    current_count += 1
    if current_count % 2 != 0:
            ans += 1
else:
    if current_count % 2 != 0:
            ans += 1
    ans += 1
print(ans)
import sys
from math import factorial
from fractions import Fraction
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
s = input()

if n %2 == 0:
    print('No')
else:
    flag = True
    for i in range(n):
        if s[i] != s[n//2 + i]:
            flag = False
    if flag:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import sys
from math import factorial
from fractions import Fraction
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
s = input()

if n%2 == 1:
    print('No')
else:
    flag = True
    for i in range(n//2):
        if s[i] != s[n//2 + i]:
            flag = False
    if flag:
        print('Yes')
    else:
        print('No')
n, m, k = map(int, input().split())

fr = [set() for _ in range(n)]
bl = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    fr[a-1].add(b-1)
    fr[b-1].add(a-1)
    
for i in range(k):
    c ,d = map(int, input().split())
    bl[c-1].add(d-1)
    bl[d-1].add(c-1)
    

def connectedcomponents():
    visited = []
    cc = []
    for i in range(n):
        visited.append(False)
    for v in range(n):
        if visited[v] == False:
            temp = set()
            cc.append(dfs(fr,v,temp,visited))
    return cc
            

def dfs(fr, v, temp, visited):
    visited[v] = True
    temp.add(v)
    for i in fr[v]:
        if visited[i] == False:
            temp = dfs(fr, i, temp, visited)
    return temp

cc = connectedcomponents()

ans = []
for i in range(n):
    for component in cc:
        if i in component:
            aa = len(component) - len(component & fr[i]) - len(component & bl[i]) - 1
            ans.append(aa)
print(*ans)

### FIXED CODE ###


from sys import setrecursionlimit 
setrecursionlimit(10**6)

n, m, k = map(int, input().split())

fr = [set() for _ in range(n)]
bl = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    fr[a-1].add(b-1)
    fr[b-1].add(a-1)
    
for i in range(k):
    c ,d = map(int, input().split())
    bl[c-1].add(d-1)
    bl[d-1].add(c-1)
    

def connectedcomponents():
    visited = []
    cc = [0]*n
    for i in range(n):
        visited.append(False)
    for v in range(n):
        if visited[v] == False:
            temp = set()
            for i in dfs(fr,v,temp,visited):
                cc[i] = dfs(fr,v,temp,visited)
    return cc
            

def dfs(fr, v, temp, visited):
    visited[v] = True
    temp.add(v)
    for i in fr[v]:
        if visited[i] == False:
            temp = dfs(fr, i, temp, visited)
    return temp

cc = connectedcomponents()

ans = []
for i in range(n):
    aa = len(cc[i]) - len(cc[i] & fr[i]) - len(cc[i] & bl[i]) - 1
    ans.append(aa)
print(*ans)
p=[]
q=[]
n,m = map(int,input().spplit())
for _ in [0]*m:
  a,b = map(int,input().spplit())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
for x in p:
  if x in q:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

### FIXED CODE ###

p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
p.sort()
q.sort()
i,j = 0,0
while i<len(p) and j<len(q):
    if p[i]<q[j]:
      i += 1
    elif p[i]>q[j]:
      j += 1
    else:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")
n,m = map(int, input().split())
 
arS = [False] * (n+1)
 
score = 0
penalty = 0
for i in range(m):
	id, res = input().split()
	id = int(id)
#	print(type(id),type(res))
	if (res == "AC") and (arS[id]==False):
		arS[id] = True
		score = score+1
	if (res == "WA")  # and (arS[id]==False): 
		penalty = penalty + 1
        
print(score, penalty)

### FIXED CODE ###

n,m = map(int, input().split())
 
arS = [False] * (n+1)
arP = [False] * (n+1)
 
score = 0
penalty = 0

for i in range(m):
	id, res = input().split()
	id = int(id)
	if (res == "AC") and (arS[id]==False):
		arS[id] = True
		score = score+1
		penalty = penalty + arP[id]
	if (res == "WA"): 
		arP[id] = arP[id] + 1
        
print(score, penalty)
n,k = map(int,input().split())
l = list(map(int,input().split()))
ls = []
for i in range(n-k):
  if l[i] <0 and l[i+k-1]<0:
    ls.append(abs(l[i]))
  elif l[i] >0 and l[i+k-1]>0:
    ls.append(abs(l[i+k-1]))
  elif l[i] <0 and l[i+k-1]>0:
    ls.append(2*min(abs(l[i]),l[i+k-1]) + max(abs(l[i]),l[i+k-1]))
print(min(ls))

### FIXED CODE ###

n,k = map(int,input().split())
l = list(map(int,input().split()))
ls = []
for i in range(n-k+1):
  a = l[i]
  b = l[i+k-1]
  ls.append(min(abs(a)+abs(a-b), abs(b)+abs(a-b)))
print(min(ls))
a,b,c=map(int,input().split())
numlist=a,b,c
print(numlist.sort())

### FIXED CODE ###

a,b,c=map(int,input().split())
d=sorted([a,b,c])
print ("{0} {1} {2}".format(d[0],d[1],d[2]))
N = int(input())
C = [-1]

prev = -1
for _ in range(N):
    c = int(input())
    if c == prev:
        continue
    else:
        C.append(c)
        prev = c

MOD = 10**9+7
n = len(C)-1
dp = [0]*(n+1)
last = [-1]*(n+1)
dp[0] = 1
for i in range(1, n+1):
    if last[C[i]] == -1:
        last[C[i]] = i
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1]+dp[last[C[i]]]
        dp[i] %= MOD
        last[C[i]] = i
print(dp[-1])


### FIXED CODE ###

N = int(input())
C = [-1]

for _ in range(N):
    c = int(input())
    if c == C[-1]:
        continue
    else:
        C.append(c)

MOD = 10**9+7
dp = 1
prev = [0]*(max(C)+1)

for c in C[1:]:
    dp = (dp+prev[c]) % MOD
    prev[c] = dp
print(dp)
import sys

mp = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

if __name__ == '__main__':
    n, m = map(int, input().split())
    a = sorted(input().split(), reverse=True)

    dp = [-10007] * (n + 1)
    dp[0] = 0
    for i in a:
        step = mp[int(i)]
        for j in range(step, n + 1):
            dp[j] = max(dp[j - step] + 1, dp[j])

    i = n
    while i > 0:
        for x in a:
            step = mp[int(x)]
            if dp[i - step] == dp[i] - 1:
                sys.stdout.write(x)
                i -= step
                break
    print()


### FIXED CODE ###

import sys

mp = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

if __name__ == '__main__':
    n, m = map(int, input().split())
    a = sorted(input().split(), reverse=True)

    dp = [-10007] * (n + 1)
    dp[0] = 0
    for i in a:
        step = mp[int(i)]
        for j in range(step, n + 1):
            dp[j] = max(dp[j - step] + 1, dp[j])

    i = n
    while i > 0:
        for x in a:
            step = mp[int(x)]
            if i >= step and dp[i - step] == dp[i] - 1:
                sys.stdout.write(x)
                i -= step
                break
    print()
L,R=map(int,input().split())
mod=2019

if R>=L+2020:
    print(0)
else:
    D=list(range(L,R+1))

    L=len(D)

    ANS=1<<40

    for i in range(L-1):
        for j in range(i+1,L):
            ANS=min(ANS,D[i]*D[j]%mod)

print(ANS)
            

### FIXED CODE ###

L,R=map(int,input().split())
mod=2019

if R>=L+2020:
    print(0)
else:
    D=list(range(L,R+1))

    L=len(D)

    ANS=1<<40

    for i in range(L-1):
        for j in range(i+1,L):
            ANS=min(ANS,D[i]*D[j]%mod)

    print(ANS)
a,b,c = map (int,input().split())

int T = 0

if a+b == c:
    T = 1
elif b+c == a:
    T = 1
elif a+c == b:
    T = 1

if T == 1:
    print("YES")
else:
    print('NO')




### FIXED CODE ###


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

#list 並び替え→最初と最後足して == 真ん中　ならばYES!!!

can.sort()

if can[0]+can[1] == can[2]:
    print("Yes")
else:
    print("No")
fn main() {
    let n: i64 = read();
    let ans = lucas(n);
    println!("{}", ans);
}

fn lucas(n: i64) -> i64 {
    if n == 0 { 2 }
    else if n == 1 { 1 }
    else {
        lucas(n-1) + lucas(n-2)
    }
}

// 以下関数

use std::io::*;
use std::str::FromStr;
pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

pub const MOD: u64 = 10e9 as u64 + 7;

pub fn is_prime(n: i32) -> bool {
    if n < 2 {
        return false;
    } else if n == 2 {
        return true;
    }
    let mut i = 2;
    while i * i < n {
        if n % i == 0 {
            return false;
        } else {
            i += 1;
            continue;
        }
    }
    true
}

pub fn lcm(mut n: i32, mut m: i32) -> i32 {
    n = if n > m { m } else { n };
    m = if n > m { n } else { m };
    let mut i = n;
    while i % m != 0 {
        i += n;
    }
    i
}

pub fn abs(n: i32) -> i32 {
    if n >= 0 {
        n
    } else {
        -n
    }
}

pub fn max(n: i32, m: i32) -> i32 {
    if n >= m {
        n
    } else {
        m
    }
}

pub fn min(n: i32, m: i32) -> i32 {
    if n <= m {
        n
    } else {
        m
    }
}

### FIXED CODE ###

n = int(input())
luca = [2, 1]
for i in range(n-1):
    luca.append(luca[-2] + luca[-1])

ans = luca[-1]
print(ans)
x,n= list(map(int, input().split()))
p = list(map(int, input().split())) 
import numpy as np
def getNearestValue(list, num):
    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]
if x not in p:
    print(x)
else:
    t = [i for i in range(100)]
    for i in range(n):    
        t.remove(p[i])
    print(getNearestValue(t, x))


### FIXED CODE ###

x,n= list(map(int, input().split()))
p = list(map(int, input().split())) 
import numpy as np

if x not in p:
    print(x)
else:
    t = [i for i in range(-101,201)]
    for i in range(n):    
        t.remove(p[i])
#         print(t)

    res = 100
    s = 1000
    for i in range(len(t)):
#         print(t[i])
        if s >= abs (x - t[len(t)-1-i]):
            s = abs (x - t[len(t)-1-i])
            res = t[len(t)-1-i]
    print(res)
def get_difference():
	# get input from raw_input()
	n, k = map(int, raw_input().split(' '))
	l = [int(e) for e in raw_input().split(' ')]
	if n < 1:
		print "IMPOSSIBLE"
		return
	if n == 1:
		if l[0] == k:
			print "POSSIBLE"
		else:
			print "IMPOSSIBLE"
		return
	if k in l:
		print "POSSIBLE"
		return
	if k > max(l):
		print "IMPOSSIBLE"
		return
	gcd_v = reduce(gcd, l)
	if k % gcd_v == 0 or gcd_v == 1:
		print "POSSIBLE"
	else:
		print "IMPOSSIBLE"


if __name__ == "__main__":
	get_difference()

### FIXED CODE ###

from fractions import gcd
N, K = map(int, raw_input().split(' '))
A = map(int, raw_input().split(' '))
 
M = max(A)
G = reduce(gcd, sorted(A))
 
if not K % G and K <= M:
    print 'POSSIBLE'
else:
    print 'IMPOSSIBLE'
C = input()

print(char(ord(C)+1))

### FIXED CODE ###

C = input()
 
print(chr(ord(C)+1))
N = int(input())
A = list(map(int, input().split()))
L, R, df = 0, N - 1, A[0] - A[N - 1]

while R - L > 1:
    if df < 0:
        L += 1,
        df += A[L]
    else:
        R -= 1
        df -= A[R]
print(abs(sumL_R))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
L, R, sumL_R = 0, N - 1, A[0] - A[N - 1]

while R - L > 1:
    if sumL_R < 0:
        L += 1
        sumL_R += A[L]
    else:
        R -= 1
        sumL_R -= A[R]
print(abs(sumL_R))
A = int(input())
B = int(input())

if A<9 and B<9:
 print("Yay!")
else:
 print(":(")

### FIXED CODE ###

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

if A<9 and B<9:
 print("Yay!")
else:
 print(":(")
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
V = IL()
C = IL()

ans = 0
for i in range(N):
    v = V[i]
    c = C[i]
    if v-c > 0:
        ans += v-c

print(ans)

### FIXED CODE ###

import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
V = IL()
C = IL()

ans = 0
for i in range(N):
    v = V[i]
    c = C[i]
    if v-c > 0:
        ans += v-c

print(ans)
n=int(input())
lst=[]
for i in range(n):
  a,b,c=map(int,input().split())
  lst.append([a,b,c])
C=[[float('inf')]*3]*n
C[0][0]=lst[0][0]
C[0][1]=lst[0][1]
C[0][2]=lst[0][2]
D=[0,1,2]
d=D
for i in range(n-1):
  for j in d:
    D=d
    D.remove(j)
    C[i+1][j]=max(C[i][D[0]],C[i][D[1]])
print(max(C[n-1]))
      
    
  
  


### FIXED CODE ###

n=int(input())
lst=[]
for i in range(n):
  a,b,c=map(int,input().split())
  lst.append([a,b,c])
C=[]
for i in range(n):
    C.append([float('inf')]*3)
C[0][0]=lst[0][0]
C[0][1]=lst[0][1]
C[0][2]=lst[0][2]
D=[0,1,2]
for i in range(n-1):
  for j in [0,1,2]:
    del D[j]
    C[i+1][j]=max(C[i][D[0]]+lst[i+1][j],C[i][D[1]]+lst[i+1][j])
    D=[0,1,2]
print(max(C[n-1]))
import math

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

sum_all = 0
for i in range(1, n + 1):
    sum_n = 0
    m = i
    while(m > 0):
        sum_n += math.floor(m % 10)
        m = int(m / 10)
    if a <= sum_n <= b:
        sum_all += i

print(sum_all)

### FIXED CODE ###

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

if (a + b) > (c + d):
  print('Left')
elif (a + b) < (c + d):
  print('Right')
else:
  print('Balanced')
s=str(input())

s+=1
print(s)

### FIXED CODE ###

alp=input()
ask=ord(alp)
print(chr(ask+1))
import math
def lcm(x, y):
    return (x*y) // math.gcd(x, y)


    
n = int(input())
t = []
for i in range(n):
    t.append(int(input()))
b = 1
for i in range(1, len(t)):
    
    b = lcm(t[i-1],t[i])

print(b)


### FIXED CODE ###

def gcd (a, b):
    if a < b:
        a, b = b, a
    
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm (a, b):
    return a * b // gcd(a, b)

n = int(input())
t = []
for i in range(n):
    t.append(int(input()))

b = 1
for i in range(n):
    b = lcm(b, t[i])

print(b)
from collections import Counter
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def ii(): return int(stdin.readline())
def li(): return map(int, stdin.readline().split())
def ns(): return stdin.readline().rstrip()
N = ii()
S = ns()
r = N - 1
while S[r] == "#":
    r -= 1
cnt = Counter(S[:r+1])
print(min(cnt["."], cnt["#"]))


### FIXED CODE ###

from collections import Counter
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def ii(): return int(stdin.readline())
def li(): return map(int, stdin.readline().split())
def ns(): return stdin.readline().rstrip()
N = ii()
S = ns()
bs = [0] * (N + 1)
ws = [0] * (N + 1)
total = float("inf")
left_b = 0
right_w = 0
for i, s in enumerate(S):
    if s == "#":
        left_b += 1
    bs[i + 1] = left_b
for i in reversed(range(N)):
    if S[i] == ".":
        right_w += 1
    ws[i] = right_w

for i in range(N):
    total = min(total, ws[i+1] + bs[i])

print(total)
X, Y, Z = map(int, input.split())
print(Z, X, Y)

### FIXED CODE ###

X, Y, Z = map(int, input().split())
print(Z, X, Y)
A,B=map(int.input())
if A==2 or B==2:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

A,B=map(int, input().split())
if A==2 or B==2:
  print('No')
else:
  print('Yes')
S = str(input())
if "hi" = S:
  print("Yes")
elif "hihi" = S:
  print("Yes")
elif "hihihi" = S:
  print("Yes")
elif "hihihihi" = S:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

S = str(input())
if "hi" == S:
  print("Yes")
elif "hihi" == S:
  print("Yes")
elif "hihihi" == S:
  print("Yes")
elif "hihihihi" == S:
  print("Yes")
elif "hihihihihi" == S:
  print("Yes") 
else:
  print("No")
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 ** 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 = [[] 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)

### 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)
n = int(input())

power = 1
mod = 10**9+7

for i in range(n):
  p = (p * (i+1)) % mod
print(p)

### FIXED CODE ###

n = int(input())

power = 1
mod = 10**9+7

for i in range(n):
  power = (power * (i+1)) % mod
print(power)
H,W = tuple(map(int,input().split()))

P = [[-int(i) for i in input().replace("#","0").replace(".","1")] for i in range(H)]

queue_set = set()
for h in range(H):
    for w in range(W):
        if  P[h][w]==0:
            for dh,dw in [(-1,0),(1,0),(0,-1),(0,1)]:
                if 0<=h+dh<H and 0<= w+dw <W:
                    queue_set.add((h+dh)*W+w+dw )
        elif h == 0 or h==H-1 or w==0 or w==W-1:
            queue_set.add(h*W+w)
m = 0

queue = [[q//W,q%W,0] for q in  queue_set]


while len(queue) != 1:
    h,w,cnt = queue.pop(0)
    if P[h][w] == -1:
        P[h][w] = cnt+1
        a = 0
        for dh,dw in [(-1,0),(1,0),(0,-1),(0,1)]:
            if 0<=h+dh<H and 0<= w+dw <W:
                a = max(P[h+dh][w+dw],a)
                if P[h+dh][w+dw]==-1:
                    queue+=[[h+dh,w+dw,cnt+1]]       
        m = max(m, cnt+1 + a)

print(m)

### FIXED CODE ###

H, W = tuple(map(int, input().split()))
func = (lambda x: 0 if x == "#" else -1)
func_in = (lambda h, w: 0 <= h < H and 0 <= w < W)
P = [[func(i) for i in input()] for i in range(H)]

queue_set = set()
zeros = set()
for h in range(H):
    for w in range(W):
        if P[h][w] == 0:
            zeros.add((h)*W+w)
            for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                if func_in(h+dh, w+dw) and P[h+dh][w+dw] == -1:
                    queue_set.add((h+dh)*W+w+dw)
m = 0

queue = [[q // W, q % W, 0] for q in queue_set]
queue_set |= zeros
idx = 0
cnt = 0
while len(queue) > idx:
    h, w, cnt = queue[idx]
    idx += 1
    cnt += 1
    P[h][w] = cnt
    a = 0
    for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if func_in(h+dh, w+dw) and (h+dh)*W+w+dw not in queue_set:
            queue += [[h + dh, w + dw, cnt]]
            queue_set.add((h+dh)*W+w+dw)
print(cnt)