Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]


# In[14]:


"""
def binary_search(nbs, tar):
    #print(nbs, tar)
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln < rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値がtarより大きければ、
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t
"""


# In[16]:


sbcs = sorted(bcs, key=lambda x:x[1], reverse=True)
sA = sorted(A)

nb = 0
ans = 0
is_finish = False

for i in range(M):
    B, C = sbcs[i]
    
    for j in range(B):
        if nb < N and A[nb+i] < C:
            ans += C
            nb += 1
        else:
            is_finish = True
            break
    
    if is_finish:
        break

if nb < N:
    ans += sum(A[nb:])

print(ans)
        
"""
    if nb >= N: # nbがN以上になれば、終了
        break
    
    B, C = sbcs[i]
    las = nb+B-1
    las = las if las <N else N-1
    if sA[nb] >= C: # もしnb個目がC以上であれば、終了
        break
    elif sA[nb+B-1] <= C: #もしB個目が、C以下なら、B個目までをCにする
        sA[nb:nb+B] = [C]*B
        nb += B
    else: #nb個目がC未満で、nb+B-1個目がCより大きければ
        t = binary_search(sA[nb:nb+B], C) 
        t = t if nb+t < N else N-nb-1
        sA[nb:nb+t+1] = [C]*(t+1)
        nb += t+1
    
print(sum(sA))
"""


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
bcs = [list(map(int, input().split())) for i in range(M)]


# In[14]:


"""
def binary_search(nbs, tar):
    #print(nbs, tar)
    ln = 0
    rn = len(nbs)-1
    t = int(len(nbs)/2)
    
    while ln < rn:
        comp = nbs[t]
        if tar >= comp and tar<nbs[t+1]:
            break
        elif tar >= comp: # 今の値がtar以下であれば、
            ln = t + 1 # 左端をt+1に更新
        elif tar < comp: # 今の値がtarより大きければ、
            rn = t - 1 # 右端をt-1に更新
        t = int((ln+rn)/2)
    return t
"""


# In[16]:


sbcs = sorted(bcs, key=lambda x:x[1], reverse=True)
sA = sorted(A)

nb = 0
ans = 0
is_finish = False

for i in range(M):
    B, C = sbcs[i]
    
    for j in range(B):
        if nb < N and sA[nb] < C:
            ans += C
            nb += 1
        else:
            is_finish = True
            break
    
    if is_finish:
        break

if nb < N:
    ans += sum(sA[nb:])

print(ans)
        
"""
    if nb >= N: # nbがN以上になれば、終了
        break
    
    B, C = sbcs[i]
    las = nb+B-1
    las = las if las <N else N-1
    if sA[nb] >= C: # もしnb個目がC以上であれば、終了
        break
    elif sA[nb+B-1] <= C: #もしB個目が、C以下なら、B個目までをCにする
        sA[nb:nb+B] = [C]*B
        nb += B
    else: #nb個目がC未満で、nb+B-1個目がCより大きければ
        t = binary_search(sA[nb:nb+B], C) 
        t = t if nb+t < N else N-nb-1
        sA[nb:nb+t+1] = [C]*(t+1)
        nb += t+1
    
print(sum(sA))
"""


# In[ ]:
#input
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))

#output
import math
A = np.sort(A)

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

q = np.full(N, 0, int)
for i in range(N-K+1):
    q[i] = cmb(N-i-1, N-K-i)

r = -q + q[-1::-1]

print((A*r).sum() % (10**9 + 7))

### FIXED CODE ###

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

#output
import math

A.sort()
mod = 10**9+7

n_ = 10**5 + 3
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
#これだとTLE!
"""
def cmb(n, r):
    if n < r: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
"""

M = 0
m = 0
for i, a in enumerate(A):
    M += cmb(i, K-1) * a
    m += cmb(N-i-1, K-1) * a
    M %= mod
    m %= mod

print((M-m) % mod)
a, b = map(int, input().split())
print(math.gcd(a, b))

### FIXED CODE ###

x, y = map(int, input().split())
while True:
  if x >= y:
    x = x % y
  else:
    y = y % x
  if x % y == 0:
    print(y)
    break
  elif y % x == 0:
    print(x)
    break
# https://atcoder.jp/contests/abc145/tasks/abc145_d


X, Y = map(int, input().split())

if (2*Y- X) % 3 or (2*X- Y) % 3:
    print(0)
    exit()

x = (2*Y - X) // 3
y = (2*X - Y) // 3

if x <= 0 or y =< 0:
    print(0)
    exit()

n = x + y
r = x


mod = 10**9 + 7
f = 1
for i in range(1, n + 1):
    f = f*i % mod
fac = f
f = pow(f, mod-2, mod)
facinv = [f]
for i in range(n, 0, -1):
    f = f*i % mod
    facinv.append(f)
facinv.append(1)

print(fac * facinv[r] * facinv[n - r] % mod)

### FIXED CODE ###

# https://atcoder.jp/contests/abc145/tasks/abc145_d


class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

X, Y = map(int, input().split())

if (2*Y- X) % 3 or (2*X- Y) % 3:
    print(0)
    exit()

x = (2*Y - X) // 3
y = (2*X - Y) // 3

n = x + y
r = x


mod = 10**9 + 7
f = 1
for i in range(1, n + 1):
    f = f*i % mod
fac = f
f = pow(f, mod-2, mod)
facinv = [f]
for i in range(n, 0, -1):
    f = f*i % mod
    facinv.append(f)
facinv.append(1)

comb = Combination(n)
print(comb.C(n,r))
D,G=map(int,input().split())
A=[]
for i in range(D):
    p,c=map(int,input().split())
    A.append([p,c])
a=10**9
for j in range(2**D):
    b=format(j, 'b')
    B="0"*(D-len(b))+str(b)
    S=[]
    N=[]
    for k in range(D):
        S.append((A[k][0]*(k+1)*100+A[k][1])*int(B[-k-1]))
        N.append(A[k][0]*int(B[-k-1]))
        if sum(S)>=G:
            s=sum(N)
            if a>s:
                a=s
        else:
            for l in range(D):
                if B[l]=="0" and (G-sum(S))<=((D-l)*100)*(A[-l-1][0]-1) :
                    s=sum(N)+((G-sum(S))//((D-l)*100))+min(1,((G-sum(S))%((D-l)*100)))
                    break
            if a>s:
                a=s
print(a)

### FIXED CODE ###

D,G=map(int,input().split())
A=[]
for i in range(D):
    p,c=map(int,input().split())
    A.append([p,c])
a=10**9
for j in range(2**D):
    b=format(j, 'b')
    B="0"*(D-len(b))+str(b)
    S=[]
    N=[]
    for k in range(D):
        S.append((A[k][0]*(k+1)*100+A[k][1])*int(B[-k-1]))
        N.append(A[k][0]*int(B[-k-1]))
        if sum(S)>=G:
            s=sum(N)
            if a>s:
                a=s
        else:
            for l in range(D):
                if B[l]=="0" and (G-sum(S))<=((D-l)*100)*(A[-l-1][0]-1):
                    s=sum(N)+((G-sum(S))//((D-l)*100))+min(1,((G-sum(S))%((D-l)*100)))
                    if a>s:
                        a=s
                    break
print(a)
n,m=map(int, input().split())  #複数数値入力

import sys

sys.setrecursionlimit(10**9)

if m == 0:
    print(countWays_memo(n))
else:
    list_a = []
    for i in range(m):
        list_a.append(int(input()))

    def countWays_memo(n):
        memo = [-1]*(n+1)
        def _countWays(n):
            if n < 0:
                return 0
            elif n == 0:
                return 1
            else:
                if memo[n] > -1:
                    return memo[n]
                else:
                    memo[n] = _countWays(n-1) + _countWays(n-2) 
                    return memo[n]
        return _countWays(n)

    steps = [list_a[0]]
    now_step=list_a[0]+1
    for i in range(len(list_a)-1):
        steps.append(list_a[i+1]-now_step)
        now_step = list_a[i+1]+1
    steps.append(n-now_step+1)


    dict_steps = {}
    for s in set(steps):
        dict_steps[s] = steps.count(s)

    ans = 1
    for k,v in dict_steps.items():
        ans *= countWays_memo(k-1)**v

    print(ans% 1000000007)

### FIXED CODE ###

n,m=map(int, input().split())  #複数数値入力

import sys

sys.setrecursionlimit(10**9)

def countWays_memo(n):
    memo = [-1]*(n+1)
    def _countWays(n):
        if n < 0:
            return 0
        elif n == 0:
            return 1
        else:
            if memo[n] > -1:
                return memo[n]
            else:
                memo[n] = _countWays(n-1) + _countWays(n-2) 
                return memo[n]
    return _countWays(n)
    
if m == 0:
    print(countWays_memo(n)% 1000000007)
else:
    list_a = []
    for i in range(m):
        list_a.append(int(input()))

    steps = [list_a[0]]
    now_step=list_a[0]+1
    for i in range(len(list_a)-1):
        steps.append(list_a[i+1]-now_step)
        now_step = list_a[i+1]+1
    steps.append(n-now_step+1)


    dict_steps = {}
    for s in set(steps):
        dict_steps[s] = steps.count(s)

    ans = 1
    for k,v in dict_steps.items():
        ans *= countWays_memo(k-1)**v

    print(ans% 1000000007)
def pdebut(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
		if o<0 : return False
	return o>=0
	
def pfin(s):
	c = 0
	for o in s[::-1]:
		if o==')':
			c+=1
		else:c-=1
		if c<0: return False
	return c>=0
	
def valuer(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
	return o
	
n = int(input())
val = [0]*(n+1)
tab = []
debut = []
fin = []
milieu = []
for i in range(n):
	s = input()
	tab.append(s)
	if pdebut(s):
		debut+=[i]
	elif pfin(s):
		fin+=[i]
	else:
		val[i] = valuer(s)
		milieu+=[i]

# ~ def cle(x):
	# ~ return -x[1]		
# ~ couples = [[i,val[i]] for i in milieu]
# ~ couples.sort(key = cle)

S = "".join(tab[i] for i in debut)
S+="".join(tab[c[0]] for c in couples)
S+= "".join(tab[i] for i in fin)

# ~ print("debut",debut)
# ~ print("milieu",milieu)
# ~ print("fin",fin)

# ~ print(S)

def Bon(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
		if o<0 : return False
	return o==0
print("Yes" if Bon(S) else "No")


### FIXED CODE ###

def pdebut(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
		if o<0 : return False
	return o>=0
	
def pfin(s):
	c = 0
	for o in s[::-1]:
		if o==')':
			c+=1
		else:c-=1
		if c<0: return False
	return c>=0
	
def valuer(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
	return o
	
n = int(input())
val = [0]*(n+1)
tab = []
debut = []
fin = []
milieu = []
for i in range(n):
	s = input()
	tab.append(s)
	if pdebut(s):
		debut+=[i]
	elif pfin(s):
		fin+=[i]
	else:
		val[i] = valuer(s)
		milieu+=[i]

def cle(x):
	return -x[1]		
couples = [[i,val[i]] for i in milieu]
couples.sort(key = cle)

S = "".join(tab[i] for i in debut)
S+="".join(tab[c[0]] for c in couples)
S+= "".join(tab[i] for i in fin)

# ~ print("debut",debut)
# ~ print("milieu",milieu)
# ~ print("fin",fin)

# ~ print(S)

def Bon(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
		if o<0 : return False
	return o==0
print("Yes" if Bon(S) else "No")
# ARC100D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


import numpy as np
import bisect
n = int(input())
a = np.array(list(map(int, input().split())))
ca = [None] * n #ca[i] = a0~aiの和
# s = 0
# for i,num in enumerate(a):
#     s += a[i]
#     ca[i] = s
ca = a.cumsum()

def sub(l, init):
    if len(l)==0:
        return 0,0
    elif len(l)==1:
        return 0,l[0]-init
    target = (init + l[-1])/2
    i = bisect.bisect_right(l, target)
    p1 = (l[i]-init, l[-1]-l[i])
    p2 = (l[i-1]-init, l[-1]-l[i-1])
    if abs(p1[0] - p1[1]) < abs(p2[0] - p2[1]):
        return min(p1), max(p1)
    else:
        return min(p2), max(p2)
best = 10**15
for i in range(1,n):
    p1 = sub(ca[:i], 0)
    p2 = sub(ca[i:], ca[i-1])
    nn = max(p1[1]-p2[0], p2[1]-p1[0], p1[1]-p1[0], p2[1]-p2[0])
    best = min(best, nn)
print(best)

### FIXED CODE ###

# ARC100D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


# import numpy as np
import bisect
n = int(input())
a = list(map(int, input().split()))
# a = np.array(list(map(int, input().split())))
ca = [None] * n #ca[i] = a0~aiの和
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s
# ca = a.cumsum()

def sub(l, start, end, init):
    if len(l)==0:
        return 0,0
    elif end-start==1:
        return 0,l[start]-init
    target = (init + l[end-1])/2
    i = bisect.bisect_right(l, target)
    p1 = (l[i]-init, l[end-1]-l[i])
    p2 = (l[i-1]-init, l[end-1]-l[i-1])
    if abs(p1[0] - p1[1]) < abs(p2[0] - p2[1]):
        return min(p1), max(p1)
    else:
        return min(p2), max(p2)
best = 10**15
for i in range(1,n):
    p1 = sub(ca, 0, i, 0)
    p2 = sub(ca, i, n, ca[i-1])
    nn = max(p1[1]-p2[0], p2[1]-p1[0], p1[1]-p1[0], p2[1]-p2[0])
#     print(p1,p2,nn)
    best = min(best, nn)
print(best)
N = int(input())
all_yen = 0
for n in range(N):
    x , u = input().split()
    if u  == 'BTC':
        x *= 380000.0

    all_yen += x




### FIXED CODE ###

N = int(input())
all_yen = 0
for n in range(N):
    x , u = input().split()
    x = float(x)
    if u == 'BTC':
        x *= 380000.0
        
    all_yen += x

print(all_yen)
import fractions

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

def l(m): #左m個
    if m == 0:
        return 0
    else:
        return fractions.gcd(l(m-1),a[m-1])
def r(m):  #右m個
    if m == 0:
        return 0
    else:
        return fractions.gcd(r(m-1),a[n-m])
max([fractions.gcd(l(i),r(n-i-1)) for i in range(n)])

### FIXED CODE ###

def gcd(x,y):
    while y != 0:
        x,y = y,x%y
    return x
n = int(input())
a = list(map(int,input().split()))

L,R = [0],[0]
for i in range(1,n+1): #L[i]は左i個,R[i]は右i個
    L.append(gcd(L[-1],a[i-1]))
    R.append(gcd(R[-1],a[n-i]))
print(max(gcd(L[i],R[n-i-1]) for i in range(n)))
n,a,b = list(map(int,input().split()))
mod = 10**9 + 7
ans = (pow(2,n,mod) - 1
numerator = 1
denominator = 1

for i in range(1,n+1):
    numerator = (numerator*(n-i+1))%mod
    denominator = (denominator*i)%mod
    if i == a or i == b:
        ans = ans - (numerator*pow(denominator,mod-2,mod))%mod
        if i == b:
            break

print(ans%mod)

### FIXED CODE ###

n,a,b = list(map(int,input().split()))
mod = 10**9 + 7

ans = (pow(2,n,mod) - 1) %mod
numerator = 1%mod
denominator = 1%mod
for i in range(1,b+1):
    numerator = (numerator*(n+1-i))%mod
    denominator = (denominator*pow(i,mod-2,mod))%mod
    if i == a or i == b:
        ans = (ans - (numerator*denominator))%mod

print(ans)
import numpy as np
A, B, C, D = map(int, input().split())
s = np.array(list(range(A, B + 1)))
s = s[s % C != 0]
t = s[s % D != 0]
s = set(s)
t = set(t)
print(len(s & t))

### FIXED CODE ###

from fractions import gcd
A, B, C, D = map(int, input().split())
CD = C * D // gcd(C, D)

U = B - A + 1
U_c = (B // C) - (A // C) + int(A % C == 0)
U_d = (B // D) - (A // D) + int(A % D == 0)
U_cd = (B // CD) - (A // CD) + int(A % CD == 0)

ans = U - (U_c + U_d - U_cd)
print(ans)
X, Y = map(int, input().split())
dic = {'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15}
if dic[X] > dic[Y]:
  print('>')
elif dic[X] == dic[Y]:
  print('=')
else:
  print('<')
  

### FIXED CODE ###

X, Y = input().split()
dic = {'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15}
if dic[X] > dic[Y]:
  print('>')
elif dic[X] == dic[Y]:
  print('=')
else:
  print('<')
N = int(input())

edges = [[] for _ in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    edges[u-1].append((v-1, w))
    edges[v-1].append((u-1, w))

dist = [0 for _ in range(N)]
def measure(src):
    """
    srcを根とした木に対し、根から各頂点までの距離を求める
    """
    for v, w in edges[src]:
        dist[v] = dist[src] + w
        measure(v) 
measure(0)

for i in range(N):
    if dist[i] % 2:
        print(1)
    else:
        print(0)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N = int(input())

edges = [[] for _ in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    edges[u-1].append((v-1, w))
    edges[v-1].append((u-1, w))

dist = [-1 for _ in range(N)]
def measure(src):
    """
    srcを根とした木に対し、根から各頂点までの距離を求める
    """
    for v, w in edges[src]:
        if dist[v] == -1:
            dist[v] = dist[src] + w
            measure(v)

dist[0] = 0
measure(0)

for i in range(N):
    if dist[i] % 2:
        print(1)
    else:
        print(0)
mport itertools
import math
N=int(input())
a=[]
kyori_list=[]
for i in range(N):
    x,y=map(int,input().split())
    a.append((x,y))
for j in itertools.permutations(a):
    k=list(j)
    
    cnt=0
    sum=0
    while cnt<N-1:
        kryoi=0
        kyori=((k[cnt+1][0]-k[cnt][0])**2+(k[cnt+1][1]-k[cnt][1])**2)**(1/2)
        cnt+=1
        
        sum+=kyori
    kyori_list.append(sum)
c=0

for i in kyori_list:
    c+=i
    
    
print(c/math.factorial(N))

### FIXED CODE ###

import itertools
import math
N=int(input())
a=[]
kyori_list=[]
for i in range(N):
    x,y=map(int,input().split())
    a.append((x,y))
for j in itertools.permutations(a):
    k=list(j)
    
    cnt=0
    sum=0
    while cnt<N-1:
        kryoi=0
        kyori=((k[cnt+1][0]-k[cnt][0])**2+(k[cnt+1][1]-k[cnt][1])**2)**(1/2)
        cnt+=1
        
        sum+=kyori
    kyori_list.append(sum)
c=0

for i in kyori_list:
    c+=i
    
    
print(c/math.factorial(N))
while 1:
    n=int(input())
    if n=='0': break
    for _ in range(n):
        a=list(map(int,input().split()))
        c=sum(a)
        if sum(a[:2])/2>=90 or c/3>=80 or 100 in a: b='A'
        elif c/3>=70 or (c/3>=50 and (a[0]>=80 or a[1]>=80)): b='B'
        else: b='C'
        print(b)

### FIXED CODE ###

while 1:
    n=int(input())
    if n==0: break
    for _ in range(n):
        a=list(map(int,input().split()))
        c=sum(a)
        if sum(a[:2])>179 or c>239 or 100 in a: b='A'
        elif c>209 or (c>149 and max(a[:2])>79): b='B'
        else: b='C'
        print(b)
from collections import deque

def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    Q = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                Q.append((h,w))
    visited = [[0] * W for _ in range(H)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while Q:
        x, y = Q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < W and 0 <= ny < H and not visited[ny][nx]:
                visited[ny][nx] = visited[y][x] + 1
                Q.append((ny,nx))

    ans = 0
    for h in range(H):
        ans = max(ans, max(visited[h]))

    print(ans)




if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(4100000)
def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    Q = deque([])
    visited = [[float('inf')] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                Q.append((h,w))
                visited[h][w] = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    ans = 0
    while Q:
        y, x = Q.popleft()
        now = visited[y][x]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < W and 0 <= ny < H:
                if visited[ny][nx] == float('inf'):
                    visited[ny][nx] = now + 1
                    Q.append((ny,nx))
                    ans = max(ans, now + 1)

    print(ans)




if __name__ == "__main__":
    main()
N,K = map(int,input().split())
edge = [[] for i in range(N)] #隣接リスト
for i in range(N-1) :
    u,v = map(lambda x: int(x)-1, input().split())
    edge[u].append(v)
    edge[v].append(u)

deg = [len(E) for E in edge] #隣接頂点数

MOD = 10**9 + 7
u = 10**5 + 1

fact = [1]*(u+1)
for i in range(1, len(fact)) :
    fact[i] = (fact[i-1] * i) % MOD

fact_inv = [1]*(u+1)
fact_inv[u] = pow(fact[u], MOD-2, MOD)
for i in range(u-1,0,-1) :
    fact_inv[i] = (fact_inv[i+1] * (i+1)) % MOD

def perm(n, k) : #nPk
    if k < 0 or n < k :
        return 0
    return (fact[n] * fact_inv[n-k]) % MOD

def F(node, parent=None) :
    if parent is None :
        res = perm(K, deg[node] + 1) #根は自身の場合の数を計算する
    else :
        res = perm(K-2, deg[node] - 1) #根以外は自身の場合の数を計算しない. 親は計算済みなので,差し引く.
    
    for next_node in edge[node] :
        if next_node == parent :
            continue
        res *= F(next_node, parent=node)
        res %= MOD
    return res

ans = F(0, parent=None)

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N,K = map(int,input().split())
edge = [[] for i in range(N)] #隣接リスト
for i in range(N-1) :
    u,v = map(lambda x: int(x)-1, input().split())
    edge[u].append(v)
    edge[v].append(u)

deg = [len(E) for E in edge] #隣接頂点数

MOD = 10**9 + 7
u = 10**5 + 1

fact = [1]*(u+1)
for i in range(1, len(fact)) :
    fact[i] = (fact[i-1] * i) % MOD

fact_inv = [1]*(u+1)
fact_inv[u] = pow(fact[u], MOD-2, MOD)
for i in range(u-1,0,-1) :
    fact_inv[i] = (fact_inv[i+1] * (i+1)) % MOD

def perm(n, k) : #nPk
    if k < 0 or n < k :
        return 0
    return (fact[n] * fact_inv[n-k]) % MOD

def F(node, parent=None) :
    if parent is None :
        res = perm(K, deg[node] + 1) #根は自身の場合の数を計算する
    else :
        res = perm(K-2, deg[node] - 1) #根以外は自身の場合の数を計算しない. 親は計算済みなので,差し引く.
    
    for next_node in edge[node] :
        if next_node == parent :
            continue
        res *= F(next_node, parent=node)
        res %= MOD
    return res

ans = F(0, parent=None)

print(ans)
a, b = map(int, input.split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")

### FIXED CODE ###

a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")
N = int(input())
A = int(input())
B = int(input())
if N == 1:
    print('Hello World')
else:
    print(A+B)

### FIXED CODE ###

N = int(input())
if N == 1:
    print('Hello World')
else:
    A = int(input())
    B = int(input())
    print(A+B)
S = input();
 
if S[2]==S[3] & S[4]==S[5]:
  print("Yes");
else:
  print("No");

### FIXED CODE ###

S = input();
 
if S[2]==S[3] and S[4]==S[5]:
  print("Yes");
else:
  print("No");
X=input()
if X<30:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

X=int(input())
if X<30:
  print('No')
else:
  print('Yes')