Harryxun/stf_run huggingface dataset:
import math
n, x = map(int,input().split())
x_list = list(map(int,input().split()))
x_list.append(x)
x_list.sort()
dis_list = []
for i in range(n):
    dis_list.append(x_list[i+1]-x_list[i])

ans = dis_list[0]
for i in range(n):
    ans = math.gcd(dis_list[i],ans)

print(ans)

### FIXED CODE ###

from fractions import gcd

n, x = map(int,input().split())
x_list = list(map(int,input().split()))
x_list.append(x)
x_list.sort()
dis_list = []

for i in range(n):
    dis_list.append(x_list[i+1] - x_list[i])

ans = dis_list[0]
for i in range(n):
    ans = gcd(dis_list[i],ans)

print(ans)
n, tracks = list(map(int, inpput().split()))
loads = []
for _ in range(n):
    loads.append(int(input()))

# print(loads)
slices = []
min_load = [99999999999999]

@lru_cache()
def slicing(rest, s=0):
    if not rest:
        # slices.append(s+[(len(s) and s[-1][1], len(loads))])
        return sum(loads[s:])

    result = 99999999999999
    for s1 in range(s+1, len(loads)-rest+1):
        result = min(result, max(sum(loads[s: s1]), slicing(rest-1, s1)))
    return result


rs = slicing(tracks-1)
print(rs)
# print(slices)


# def load_count_max(load):
#     print(load, max(sum(loads[l[0]: l[1]]) for l in load))
    # return max(sum(loads[l[0]: l[1]]) for l in load)


# result = min(map(load_count_max, slices))
# print(result)



### FIXED CODE ###

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


def check(p):
    i = 0
    for j in range(k):
        s = 0
        while s + T[i] <= p:
            s += T[i]
            i += 1
            if i == n:
                return n
    return i


def solve():
    left = 0
    right = 100000 * 10000
    while right - left > 1:
        mid = (left + right) // 2
        v = check(mid)
        if v >= n:
            right = mid
        else:
            left = mid
    return right


T = []
for _ in range(n):
    T.append(int(input()))
ans = solve()
print(ans)
def main():
    s = input()
    m = int(s) // 2019 / 10 ** 5
    l = [0 for _ in range(len(s))]
    for i in range(1, len(s) + 1):
        x = int(s[-i:])
        l[-i] = x % 2019
    ans = 0
    for i in range(4, len(s) + 1, 1):
        for j in range(0, i - 3, 1):
            if j == 0:
                x = l[-i]
            else:
                x = l[-i] - l[-j]
            if x % 2019 == 0:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    s = input()

    n = 2019
    l = [0]
    t = 1
    for i, x in enumerate(s[::-1]):
        t = t * 10 % n
        y = (l[-1] + int(x) * t) % n
        l.append(y)

    c = Counter(l)
    ans = sum([v * (v - 1) // 2 for v in c.values()])
    print(ans)


if __name__ == '__main__':
    main()
S = input()
T = input()
print(S+T)


### FIXED CODE ###

S,T = input().split()
print(T+S)
def cal(a, op, b)

if op == '+':
  a + b
elif op == '-':
  a + b
elif op == '*':
  a * b
elif op == '/':
  a / b

while 1:
  a,op,b = raw_input().split()
  if op == '?':
    break
  else:
    cal(int(a), op, int(b))

### FIXED CODE ###

def cal(a, op, b):

  if op == '+':
    r = a + b
  elif op == '-':
    r = a - b
  elif op == '*':
    r = a * b
  elif op == '/':
    r = a / b
  return r

while 1:
  a,op,b = raw_input().split()
  if op == '?':
    break
  else:
    print(cal(int(a), op, int(b)))
N=int(input())
s=list(map(str,input().split()))
print('Three' if s.count('Y')==0 else 'Four')

### FIXED CODE ###

n=int(input())
print(n//3)
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))

def C(n,r):
    if n < 0 or r < 0 or n < r: 
        return 0
    elif n == 0 or r == 0: 
        return 1
    return C(n-1,r-1)+C(n-1,r)

def main():
    n = ni()
    l = sorted(na())
    ans = C(n, 3) // 3
    j = n - 2
    k = n - 1
    dame = []
    for i in range(n - 3, -1, -1):
        if i in dame or j in dame or k in dame:
            continue
        a = l[i]
        b = l[j]
        c = l[k]
        if a < b + c and b < a + c and c < a + b:
            j -= 1
            k -= 1
        else:
            if a > b + c:
                dame.append(i)
            if b > a + c:
                dame.append(j)
            if c > a + b:
                dame.append(k)
    
    for d in dame:
        ans -= C(n - d - 1, 1)

    nn = len(dame)
    if nn >= 3:
        j = n - 2
        k = n - 1
        for i in range(dame - 3, -1, -1):
            a = l[i]
            b = l[j]
            c = l[k]
            if a < b + c and b < a + c and c < a + b:
                ans += 1

    print(ans)

main()

### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))

from bisect import bisect_left

def main():
    n = ni()
    l = sorted(na())
    
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            t = l[i] + l[j]
            ind = bisect_left(l, t)
            ans += max(0, ind - j - 1)
    print(ans)

main()
n,k=map(int,input().split())
*s,=input()
g=[]
t=1
for i in range(1,n):
 if s[i]==s[i-1]:t+=1
 else:g.append(t);t=1
g.append(t)
for i in range(1,len(g)):g[i]+=g[i-1]
g=[0]+g+[g[-1]]
print(max(g[i]-g[max(0,i-2*k-1)]for i in range(s[0]=='1',len(g),2))

### FIXED CODE ###

n,k=map(int,input().split())
*s,=input()
g=[]
t=1
for i in range(1,n):
    if s[i]==s[i-1]:
        t+=1
    else:
        g.append(t)
        t=1
g.append(t)
for i in range(1,len(g)):
    g[i]+=g[i-1]
g=[0]+g+[g[-1]]
a=0
for i in range(s[0]=='1',len(g),2):
    a=max(a,g[i]-g[max(0,i-2*k-1)])
print(a)
N,K = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

for i in range(N):
    if 0 <= A[i]:
        P.append(A[i])
    else:
        M.append(A[i])

M.sort()

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1
elif K % 2 == 1 and len(P) == 0:
    M.sort(reverse=True)

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        Ans.append(P[p + 1])
        p += 2
    elif p+1 >= len(P):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            Ans.append(P[p + 1])
            p += 2

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)


### FIXED CODE ###

import sys

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

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

for i in range(N):
    if 0 <= A[i]:
        P.append(A[i])
    else:
        M.append(A[i])

M.sort()

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1
elif K % 2 == 1 and len(P) == 0:
    M.sort(reverse=True)
elif len(M) == 0:
    answer = 1
    for i in range(K):
        answer = (answer * P[i]) % 1000000007

    print(answer)
    sys.exit()

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M) and p < len(P):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        if p + 1 < len(P):
            Ans.append(P[p + 1])
            p += 2
        else:
            p += 1
        
    elif p+1 >= len(P) and m < len(M):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    elif m >= len(M) and p < len(P):
        Ans.append(P[p])
        p += 1
    elif p >= len(P) and m < len(M):
        Ans.append(M[m])
        m += 1
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            Ans.append(P[p + 1])
            p += 2

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)
n,l=map(int,input().split())
s=[]
for i in range(n):
    s.append(str(input()))

a="".join(sorted(s))    

             
print(a

### FIXED CODE ###

n,l=map(int,input().split())
s=[]
for i in range(n):
    s.append(str(input()))

a="".join(sorted(s))    

             
print(a)
n = int(input())
h = list(map(int,input().split(" ")))

plsl = []
plsn = 0
for i in range(n-1):
    if h[i]>= h[i+1] and i == n-2:
        plsn += 1
        # print(plsn)
        plsl.append(plsn)
        # print(plsl)
    elif h[i]>= h[i+1] and i < n-1:
        plsn += 1
        # print(plsn)
    else:
        plsl.append(plsn)
        # print(plsl)
        plsn = 0
        # print(plsn)
plsl.sort(reverse = True)
print(plsl[0])


### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
answer = -1#これなに
m = 0#カウントするやつやね
for i in range(n-1):
    if h[i] >= h[i+1]:
        m += 1
    else:
        answer = max(answer,m)
        m = 0
answer = max(answer,m)
print(answer)
import numpy as np

def divisors(n):
    divs = set()
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            divs |= {i, n//i}
    return sorted(divs)

def is_disjoint(n,m):
    return np.gcd(n,m) == 1

def appendable(list, n):
    return all(is_disjoint(l, n) for l in list)

#O(n**2)!
def filter_disjoint(divisors):
    list = []
    for d in divisors:
        if appendable(list, d):
            list.append(d) 
    return list


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

filterd = filter_disjoint(divisors(np.gcd(a,b)))
print(len(filterd))

### FIXED CODE ###

def divisors(n):
    divs = set()
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            divs |= {i, n//i}
    return sorted(divs)

def gcd(n,m):
    if m == 0:
        return n
    else:
        return gcd(m, n%m)

def is_disjoint(n,m):
    return gcd(n,m) == 1

def appendable(list, n):
    return all(is_disjoint(l, n) for l in list)

#O(n**2)!
def filter_disjoint(divisors):
    list = []
    for d in divisors:
        if appendable(list, d):
            list.append(d) 
    return list


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

filterd = filter_disjoint(divisors(gcd(a,b)))
print(len(filterd))
S = input()

def ticket_sum(i, s, num, memo):
    if i == len(S):
        if num == 7:
            memo.append(s+"=7")
            return
        else:
            return
    
    # 数字を分ける場所
    pos = i - len(S)
    
    # "+"を入れる場合
    ticket_sum(i+1, s[:pos]+"+"+s[pos:], num+int(s[pos]), memo)
    # "-"を入れる場合
    ticket_sum(i+1, s[:pos]+"-"+s[pos:], num-int(s[pos]), memo)

    return memo[0]
    
memo = []
print(ticket_sum(1, S, int(S[0]), memo))

### FIXED CODE ###

ticket = [int(i) for i in input()]
sum_list = [[] for i in range(len(ticket))]
sum_list[0] = [ticket[0]]
sign_list = [[] for i in range(len(ticket))]
sign_list[0] = [""]

for i in range(len(ticket)-1):
    for j in range(len(sum_list[i])):
        sum_list[i+1].append(sum_list[i][j] + ticket[i+1])
        sign_list[i+1].append(sign_list[i][j] + "+")
        sum_list[i+1].append(sum_list[i][j] - ticket[i+1])
        sign_list[i+1].append(sign_list[i][j] + "-")

for i in range(2**len(ticket)):
    if sum_list[len(ticket)-1][i] == 7:
        sign = sign_list[len(ticket)-1][i]
        break

for i in range(len(ticket)-1):
    print(str(ticket[i]) + sign[i], end="")
print(str(ticket[-1]) + "=7")
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] and k >= b[0]:
			x = bisect.bisect_left(b,k)
			if x >= 0 and x < len(b) and 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) and 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) and 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)
a,b=int(input())
if a==b:print(a*2)
else print(max(a,b)*2-1)

### FIXED CODE ###

a,b=map(int,input().split())
if a==b:print(a*2)
else:print(max(a,b)*2-1)
n, k = map(int, input().split())
s = input()
print(s[:k]+lower(s[k])+s[k+1:])


### FIXED CODE ###

n, k = map(int, input().split())
s = input()
print(s[:k-1]+s[k-1].lower()+s[k:])
if __name__ =="__main__":
    n = int(input())
    ls = [[int(x) for x in input().split()] for _ in range(n)]

    now_t,now_a = ls[0]

    for i in range(1,n):
        x = max([~-now_t/ls[i][0]+1 ,~-now_a/ls[i][1]+1])
        now_t,now_a = x*ls[i][0],x*ls[i][1]
    print(now_t+now_a)

### FIXED CODE ###

if __name__ =="__main__":
    n = int(input())
    ls = [[int(x) for x in input().split()] for _ in range(n)]

    now_t,now_a = ls[0]

    for i in range(1,n):
        x = max([~-now_t//ls[i][0] +1 ,~-now_a//ls[i][1] +1])
        now_t,now_a = x*ls[i][0],x*ls[i][1]
    print(now_t+now_a)
import math
n=int(input())
a=list(map(int,input().split()))
a.sort()
ls=[0]
cnt=0
for i in range(1,2**n):
  if a[i]>a[i-1]:
    cnt+1
  ls.append(cnt)
for i in range(2**n):
  if i<2**n-1:
    lmt=n-int(math.log2(n-i-1))-1
    if ls[i]<lmt:
      print("No")
      break
  if i==2**n-1:
    if ls[i]<n-1:
      print("No")
      break
else:
  print("Yes")

### FIXED CODE ###

import math
def cmb(n,r):
  return math.factorial(n)//(math.factorial(r)*math.factorial(n-r))
n=int(input())
a=list(map(int,input().split()))
a.sort()
ls=[0]
cnt=0
for i in range(1,2**n):
  if a[i]>a[i-1]:
    cnt+=1
  ls.append(cnt)
lmt = []
for i in range(n+1):
  lmt.extend([i]*cmb(n,i))
bias = ls[-1]-lmt[-1]
jdg = 0
ulmt = 0
for i in range(n):
  jdg += ls.count(i)
  ulmt += 2**(n-i-1)
  if jdg > ulmt:
    print("No")
    exit()
for x,l in zip(ls,lmt):
  if x-l > bias:
    print("No")
    break
else:
  print("Yes")
N = int(input())
v = [int(e) for e in input().split()]

a = sorted(v, reversed = True) #昇順に並べる
result = a[0]
for i in range(1, N):
    result = (result + a[i]) / 2
print(result)

### FIXED CODE ###

N = int(input())
v = [int(e) for e in input().split()]

v.sort() #昇順に並べる
result = v[0]
for i in range(1, N):
    result = (result + v[i]) / 2
print(result)
a,b=map(int,input().split())
if (a+b)%2==0:
  print(ave(a+b))
  
else:
  print('impossible')

### FIXED CODE ###

a,b=map(int,input().split())
if (a+b)%2==0:
  print((a+b)//2)
  
else:
  print('IMPOSSIBLE')
a,b,c = (int(x) for x in input().split())
if a == b:
  if a == c:
    print (1)
  else:
    pritn (2)
else:
  if a == c:
    print (2)
  else:
    print (3)


### FIXED CODE ###

a,b,c = (int(x) for x in input().split())
if a == b:
  if a == c:
    print (1)
  else:
    print (2)
else:
  if a == c:
    print (2)
  else:
    if b == c:
      print (2)
    else:
      print (3)
import numpy

### FIXED CODE ###

while True:
    try:
        a,b,c,d,e,f = (int(i) for i in input().split())
        det=a*e-b*d
        x = (c*e-b*f)/det
        y = (a*f-c*d)/det
        if x==0:x=0
        if y==0:y=0
        print("{0:.3f} {1:.3f}".format(x,y))
    except EOFError:
        break
#!/usr/bin
# -*- cording: "utf-8" -*-
 
a, b = map(int, input().split())
c = list(map(int, input().split()))
c.sort(reverse=true)
for i in range(b):
  x = x + c[i]
print(x)

### FIXED CODE ###

#!/usr/bin
# -*- cording: "utf-8" -*-
 
a, b = map(int, input().split())
c = list(map(int, input().split()))
c.sort(reverse=True)
x = 0
for i in range(b):
  x = x + c[i]
print(x)
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    q = deque()
    q.append((0, 0))
    while q:
        p, i = q.popleft()
        ai = a[i]
        for j in range(n):
            if ai[j]:
                j1 = 1 << j
                if p & j1:
                    continue
                pj1 = p | j1
                dp[pj1] += dp[p]
                if i == n: continue
                q.append((pj1, i + 1))

    print(dp[-1] % mod)


    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    b = [0]
    for i in range(n):
        b += [x + 1 for x in b]
    # print(b)
    c = [1 << i for i in range(n)]
    for i in range(n1-1):
        p = b[i]
        ap = a[p]
        for j in range(n):
            if ap[j]:
                j1 = c[j]
                if i & j1:
                    continue
                dp[i|j1] += dp[i]


    print(dp[-1] % mod)


    return


#main
if __name__ == '__main__':
    solve()
yyyy = int(input())
mm = int(input())
if yyyy < 2019:
    print('Heisei')
elif yyyy > 2019:
    print('TBD')
else:
    if mm == 1 or mm == 2 or mm == 3 or mm == 4:
        print('Heisei')
    else:
        print('TBD')

### FIXED CODE ###

S = input()
if S <= '2019/04/30' :
    print('Heisei' )
else:
    print('TBD')
import math
def gcd(n, m):
  while m % n != 0:
    m, n = n, m % n
  return m
def div(n):
  d = []
  for i in range(2, int(math.sqrt(n))+2):
    if n % i == 0:
      for j in d:
        if i % j == 0:
          break
      else:
        d.append(i)
  if len(d) == 0 and n > 1:
    return 1
  return len(d)

a, b = map(int, input().split())
if a > b:
  a, b = b, a
c = math.gcd(a,b)
print(div(c) + 1)


### FIXED CODE ###

import math
def gcd(a, b):
  while b > 0:
    a, b = b, a % b
  return a
def div(a):
  r = []
  i = 2
  k = int(math.sqrt(a))
  while i <= k:
    if a % i == 0:
      r.append(i)
      while a % i == 0:
        a //= i
      k = math.sqrt(a)
    i += 1
  if a > 1:
    r.append(a)
  return r

a, b = map(int, input().split())
if a > b:
  a, b = b, a
c = gcd(a,b)
print(len(div(c))+1)
from math import sqrt
def get_divisor(num):
	arr = [i for i in range(1,int(sqrt(num))) if num % i == 0]
	arr += [num // i for i in reversed(arr)]
	return arr

def get_common(num1, num2):
	list_a = get_divisor(num1)
	list_b = get_divisor(num2)
	return [i for i in list_a if i in list_b]

def prime_ch(num):
	if num == 1:
		return False
	for i in list(range(2,int(sqrt(num))+1)):
		if num % i == 0:
			return False
	return True


A,B = list(map(int,input().split()))[:2]
common = get_common(A,B)
c_prime = [p for p in common if prime_ch(p)]
print((len(c_prime)+1))

### FIXED CODE ###

N = int(input())
odd_count = 0
for i in range(1,N+1):
	if i % 2 == 1:
		odd_count += 1
print(odd_count/N)
n11, n12, n13 = map(int,input().split())
n21, n22, n23 = map(int,input().split())
n31, n32, n33 = map(int,input().split())
lines = [[n11,n12,n13],
         [n21,n22,n23],
         [n31,n32,n33],
         [n11,n21,n31],
         [n12,n22,n32],
         [n13,n23,n33],
         [n11,n22,n33],
         [n13,n22,n31]]
nums = {}
for i in range(int(input())):
  nums[input()] = 0
flag = False
for l in lines:
  if l[0] in nums:
    if l[1] in nums:
      if l[2] in nums:
        flag = True
if flag:
  print("No")
else:
  print("Yes")


### FIXED CODE ###

import math
s = input()
s = int(s)
s = s/2
s = math.ceil(s)
print(s)
MOD = 1000000007
N, K = map(int, input().split())
edge = {}
for _ in range(N - 1):
    a, b = map(int, input().split())
    if a not in edge:
        edge[a] = set()
    edge[a].add(b)
    if b not in edge:
        edge[b] = set()
    edge[b].add(a)


ans = K
q = [(1, None, 1)]
while len(q) > 0:
    par, parpar, depth = q.pop()
    children = edge[par] - set([parpar])
    if depth == 1:
        start = K - 1
    else:
        start = K - 2
    for i in range(len(children)):
        ans *= start - i
        ans %= MOD
    for c in children:
        q.append((c, par, depth + 1))

print(ans)


### FIXED CODE ###

MOD = 1000000007
N, K = map(int, input().split())
edge = {}
for _ in range(N - 1):
    a, b = map(int, input().split())
    if a not in edge:
        edge[a] = set()
    edge[a].add(b)
    if b not in edge:
        edge[b] = set()
    edge[b].add(a)


ans = K
q = [(1, None, 1)]
while len(q) > 0:
    par, parpar, depth = q.pop()
    if par not in edge:
        continue
    children = edge[par] - set([parpar])
    if len(children) == 0:
        continue
    if depth == 1:
        start = K - 1
    else:
        start = K - 2
    for i in range(len(children)):
        if start - i <= 0:
            ans = 0
            print(0)
            exit()
        else:
            ans *= start - i
        ans %= MOD
    for c in children:
        q.append((c, par, depth + 1))

print(ans)