Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

#ABC127 D
from operator import itemgetter as ig
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0 for i in range(M)]
C = [0 for i in range(M)]
for i in range(M):
    B[i], C[i] = map(int, input().split()) 
BC = sorted([(B[i], C[i])for i in range(M)], key = ig(1), reverse=True)
s = 0
k = 0
while(s <= N and k < M):
    D = [BC[k][1] for i in range(BC[k][0])]
    A = A + D
    s += BC[k][0]
    k += 1
print(sum(sorted(A, reverse=True)[:N]))

### FIXED CODE ###

from operator import itemgetter
n,m=map(int,input().split())
A=list(map(int,input().split()))
B=[list(map(int,input().split())) for _ in range(m)]
B.sort(key=itemgetter(1),reverse=True)
C=[]
for b,c in B:
  C+=[c]*b
  if len(C)>=n:break
print(sum(sorted(A+C)[-n:]))
### BUGGY CODE ###

N = int(input())
S = input()

result = 0
for i in range(0, 1000):
    number = ''.join(['00', str(i)])[-3:]
    number_i = 0
    for s in S:
        if number[number_i] == s:
            number_i += 1
            if number_i == 3:
                result += 1
                break

print(result)


### FIXED CODE ###

N = int(input())
S = input()

result = 0
for i in range(0, 1000):
    number = ''.join(['00', str(i)])[-3:]
    number_i = 0
    for s in S:
        if number[number_i] == s:
            number_i += 1
            if number_i == 3:
                result += 1
                break

print(result)
### BUGGY CODE ###

from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    #d = [[10 ** 12] * w for i in range(h)]
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]

ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if maze[gx][gy] == ".":
                        ans = max(ans, bfs())

print(ans)

### FIXED CODE ###

from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    #d = [[10 ** 12] * w for i in range(h)]
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]

count = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            count += 1
if count == 400:
    print(38)
    exit()

ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if sx == gx and sy == gy:
                        continue
                    if maze[gx][gy] == ".":
                        ans = max(ans, bfs())

print(ans)
### BUGGY CODE ###

s = input()
keta = len(s)
n = int(s)
infi = 10 ** 10
dp = [[infi] * (2) for _ in range(keta + 1)]
dp[0][0] = 0
for i in range(keta):
    num = int(s[-i - 1])
    for j in range(2):
        if j == 1:
            num += 1
        ni = i + 1
        if num == 10:
            nj = 1
            num = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
        elif num < 5:
            nj = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
        elif num > 5:
            nj = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 10 - num)
        else:
            nj = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
            nj = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 10 - num)
print(min(dp[keta][0], dp[keta][1] + 1))


### FIXED CODE ###

s = "0" + input()
keta = len(s)
dp = [0] * (keta + 1)
kuri = 0
for i in range(keta):
    ni = i + 1
    num = int(s[-i - 1])
    if kuri:
        num += 1
        kuri = 0
    if num == 10:
        kuri = 1
        dp[ni] = dp[i]
    elif num < 5:
        dp[ni] = dp[i] + num
    elif num > 5:
        num %= 10
        kuri = 1
        dp[ni] = dp[i] + 10 - num
    else:
        nn = int(s[-ni - 1])
        if nn < 5:
            dp[ni] = dp[i] + num
        else:
            kuri = 1
            dp[ni] = dp[i] + 10 - num
print(dp[keta] + kuri)
### BUGGY CODE ###

a, b = [int(i) for i in input().split()]
small = min(a, b)
big = max(a, b)

import sys

if small == 1:
    print(1)
    sys.exit(0)

import math
table = [i for i in range(2, small + 1) if (i % 2 != 0)]
limit  = math.sqrt(small)
prime = [2]
while True:
    if len(table) == 0:
        break
    head = table.pop(0)
    if head > limit:
        break
    table = [v for v in table if v % head != 0]
    prime.append(head)
prime.extend(table)
cd = [p for p in prime if (small % p == 0) and (big % p == 0)]

print(len(cd) + 1)


### FIXED CODE ###

a, b = [int(i) for i in input().split()]
small = min(a, b)
big = max(a, b)

import sys

if small == 1:
    print(1)
    sys.exit(0)

import math
import collections

# FYI: https://ja.wikipedia.org/wiki/%E8%A9%A6%E3%81%97%E5%89%B2%E3%82%8A%E6%B3%95
def prime_factorization(num, divisors=None):
    if num <= 1:
        assert False
    factors = []

    # divisorsを使い回せるようにする。
    #   - 二度生成した場合にかかる時間が許容できない場合
    #   - エラトステネスの篩などで素数テーブルを既に持っている場合
    if not divisors:
        divisors = [2] + [i for i in range(3, int(math.sqrt(num)) + 1) if i % 2 != 0]

    for d in divisors:
        # divisorsを引数で与えた場合のみ起こりうる
        if num < d:
            break
        while num % d == 0:
            factors.append(d)
            num //= d

    if num != 1:
        factors.append(num)
    return factors

divisors = [2] + [i for i in range(3, int(math.sqrt(big)) + 1) if i % 2 != 0]
small_factors = set(prime_factorization(small, divisors))
big_factors = set(prime_factorization(big, divisors))

print(len(small_factors.intersection(big_factors)) + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
def topological_sort(graph):
  d = {i:1 for i in nodes}
  in_cnt = {k:0 for k in nodes}
  for x in nodes:
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in nodes if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      d[y] = max(d[x]+1,d[y])
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in nodes if in_cnt[i]]:
    return None,d
  return ret,d

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now

ans,d = topological_sort(graph)
if not ans:
  print(-1)
else:
  print(max(d[i] for i in nodes))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input().strip())
M = N*(N-1)//2

graph = [[] for i in range(M)]
in_cnt = [0 for i in range(M)]
for x in range(1,N+1):
  l = list(map(int,input().split()))
  y = l[0]
  b,s = max(x,y),min(x,y)
  prev = (b-1)*(b-2)//2+s-1
  for y in l[1:]:
    b,s = max(x,y),min(x,y)
    now = (b-1)*(b-2)//2+s-1
    graph[prev].append(now)
    in_cnt[now] += 1 
    prev = now

d = [1 for k in range(M)]
q = [i for i in range(M) if not in_cnt[i]]

if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.pop()
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in range(M) if in_cnt[i]]:
  print(-1)
  exit()

print(ans)
### BUGGY CODE ###

import math
from functools import reduce


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


k = int(input())
l = []
res = 0

for i in range(k):
    for j in range(i, k):
        for m in range(j, k):
            l.append([i+1, j+1, m+1])


for i in range(len(l)):
    # print(l[i])
    if l[i][0] == l[i][1] and l[i][1] == l[i][2]:
        # print("1通り")
        # print(gcd(l[i]))
        res += gcd(l[i])
    elif l[i][0] == l[i][1] or l[i][1] == l[i][2] or l[i][0] == l[i][2]:
        # print("3通り")
        # print(gcd(l[i]))
        res += gcd(l[i])*3
    else:
        # print("6通り")
        # print(gcd(l[i]))
        res += gcd(l[i])*6

print(res)


### FIXED CODE ###

import math
from functools import reduce


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


k = int(input())
l = []
res = 0

for i in range(1, k+1):
    for j in range(i, k+1):
        for m in range(j, k+1):
            if i == j and j == m:
                res += gcd([i, j, m])
            elif i == j or j == m or i == m:
                res += gcd([i, j, m])*3
            else:
                res += gcd([i, j, m])*6
print(res)
### BUGGY CODE ###

import bisect
n, k = map(int, input().split())

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

a = sorted(a)
f = sorted(f, reverse=True)

score = sorted(((x * y, x, y) for (x, y) in zip(a, f)))
for _ in range(k):
    p, x, y = score.pop()
    if x > 0:
        x -= 1
    bisect.insort(score, (x * y, x, y))

p, _, _ = score.pop()
print(p)



### FIXED CODE ###

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

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

a = sorted(a)
f = sorted(f, reverse=True)

def judge(n):
    s = 0
    for x, y in zip(a, f):
        s += max(0, x - n // y)
    if s <= k:
        return True
    else:
        return False

low = 0
high = a[-1] * f[0]
while high - low > 0:
    mid = (high + low) // 2
    if judge(mid):
        high = mid
    else:
        low = mid + 1
print(high)
### BUGGY CODE ###

N, K = map(int, input().split())
while True:
    if K == 1:
        N=0
        break
    n = abs(N-K)
    if n >= N:
        break
    else:
        N = n
print(N)
    

### FIXED CODE ###

N, K = map(int, input().split())
n = N % K
if n > abs(n-K):
    n = abs(n-K)
print(n)
### BUGGY CODE ###

'''
参考: https://beta.atcoder.jp/contests/agc026/submissions/2849460
'''

n = int(input())
s = input()

s_left = s[:n]
s_right = s[n:]
m = dict()

for i in range(1 << n):
    s_red = s_blue = ''
    for j in range(n):
        if i & (1 << j):
            s_red = s_red  + s_left[j]
        else:
            s_blue = s_left[j] + s_blue
    if (s_red, s_blue) in m:
        m[(s_red, s_blue)] += 1
    else:
        m[(s_red, s_blue)] = 1

ans = 0
for i in range(1 << n):
    s_red = s_blue = ''
    for j in range(n):
        if i & (1 << j):
            s_red = s_right[j] + s_red
        else:
            s_blue = s_blue + s_right[j]
   
    if (s_red, s_blue) in m:
        ans += m[(s_red, s_blue)]
print(ans)


### FIXED CODE ###

def main():
    from collections import defaultdict

    N = int(input())
    S = input()

    L, R = S[:N], S[N * 2 - 1:N - 1:-1]

    def make_counter(s: str) -> defaultdict(int):
        ret = defaultdict(int)
        for bit in range(1 << N):
            red, blue = '', ''
            for j in range(N):
                if (bit >> j) & 1:
                    red += s[j]
                else:
                    blue += s[j]

            ret[red + '_' + blue] += 1
        return ret

    ld = make_counter(L)
    rd = make_counter(R)

    print(sum(ld[key] * rd[key] for key in ld))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
import math
import heapq
input = sys.stdin.readline

MOD = 10 ** 9 + 7


def main():
    N, M = map(int, input().split())
    _A = {}
    A = []

    for i in map(int, input().split()):
        if i in _A:
            _A[i] += 1
        else:
            _A[i] = 1

    for (num, c) in _A.items():
        heapq.heappush(A, (num, c))
    # B = [0] * N
    # C = [0] * N
    # print(A)

    for i in range(M):
        B, C = map(int, input().split())

        while B > 0:
            item = heapq.heappop(A)

            if item[0] < C:
                replace = min(item[1], B)
                B -= replace
                remain = item[1] - replace

                heapq.heappush(A, (C, replace))

                if remain > 0:
                    heapq.heappush(A, (item[0], remain))

                # print("")
                # print(A, B, replace)
            else:
                heapq.heappush(A, item)
                break

    ans = 0
    for a in A:
        ans += a[0] * a[1]
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
import heapq
import bisect
input = sys.stdin.readline

MOD = 10 ** 9 + 7


def main():
    N, M = map(int, input().split())
    # A = []

    # for i in map(int, input().split()):
    #     bisect.insort(A, i)

    # for i in range(M):
    #     B, C = map(int, input().split())
    _A = {}
    A = []

    for i in map(int, input().split()):
        if i in _A:
            _A[i] += 1
        else:
            _A[i] = 1

    for (num, c) in _A.items():
        heapq.heappush(A, (num, c))
    # B = [0] * N
    # C = [0] * N
    # print(A)

    B = [0] * M
    C = [0] * M
    T = [None] * M
    for i in range(M):
        b, c = map(int, input().split())
        T[i] = (c, b)

    T = sorted(T, reverse=True)

    finish = False
    for i in range(M):
        C, B = T[i]

        while B > 0:
            item = heapq.heappop(A)

            if item[0] < C:
                replace = min(item[1], B)
                B -= replace
                remain = item[1] - replace

                heapq.heappush(A, (C, replace))

                if remain > 0:
                    heapq.heappush(A, (item[0], remain))

                # print("")
                # print(A, B, replace)
            else:
                heapq.heappush(A, item)
                finish = True
                break

        if finish is True:
            break

    ans = 0
    for a in A:
        ans += a[0] * a[1]
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import bisect


N = int(input())
s = []
for i in range(N):
    si = list(input())
    si.sort()
    s += [('').join(si)]
s.sort()
ans = 0
while (s):
    t = bisect.bisect_right(s, s.pop(0))
    if t:
        del s[:t]
    ans += (t * (t + 1)) // 2
print(ans)

### FIXED CODE ###

N = int(input())
memo = {}
ans = 0
for i in range(N):
    si = list(input())
    si.sort()
    si = ('').join(si)
    if si not in memo:
        memo[si] = 1
    else:
        memo[si] += 1
        ans += memo[si] - 1
print(ans)
### BUGGY CODE ###

import numpy as np
import math
N,M = map(int,input().split())
ls = []
for n in range(N):
  ls.append(list(map(int,input().split())))
ls = np.array(ls)
idx = np.argsort(ls[:,1])[::-1]
#print (ls[idx])
days = list(range(1,M+1))
days = {k: 0 for k in days}
#print (days)
sum = 0
for work in ls[idx]:
  d = work[0]
  while(d<=M):
    if d in days:
      sum+=work[1]
      days.pop(d)
      d=M+1
    else:
      d+=1
print (sum)
  
    

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
ls = []
h = []
ans = 0
for n in range(N):
    ls.append(list(map(int,input().split())))
ls = sorted(ls,key=lambda ls:ls[0],reverse=False)
n = 0
for m in range(1,M+1):
    #print (m)
    while(n<N and ls[n][0]<=m ):
        heapq.heappush(h, -ls[n][1])
        n+=1
    if len(h)>0:
        ans -= heapq.heappop(h)
        # print (m,ans)
print (ans)
### BUGGY CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
LRC.sort()
stack=[[0,1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for l,r,c in LRC:
            if l>a:
                break
            elif a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,r])
else:
    print(-1)


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
LRC.sort()


stack=[[0,-1,0]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
visited[1]=0
x=0
while stack:
    #print(stack)
    m,a,p=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(x,M):
            l,r,c=LRC[i]
            x=i
            if l<=a:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r,a+1])
            else:
                break
else:
    print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]

    def size(self, x):
        return -self.parent[self.find(x)]

    def find(self, x):
        if (self.parent[x] < 0):
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if (x == y):
            return False
        if (self.size(x) < self.size(y)):
            self.parent[y] += self.parent[x]
            self.parent[x] = y
        else:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)


def main():
    N = int(input())
    x_list = []
    y_list = []
    x_app = x_list.append
    y_app = y_list.append
    for i in range(N):
        x, y = (int(x) for x in input().split())
        x_app([x, i])
        y_app([y, i])

    x_list.sort()
    y_list.sort()
    adj = []
    adj_app = adj.append
    for i in range(N-1):
        adj_app((x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]))
        adj_app((y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]))

    adj.sort()
    uf = UnionFind(N)
    ans = 0
    for edge in adj:
        if not uf.same(edge[1], edge[2]):
            ans += edge[0]
            uf.unite(edge[1], edge[2])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 6199094

import array
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    b = len(d[1])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        root = d[1]
        history = [1]
        a = K - 2
        while True:
            children = set()
            for i in list(root):
                b = len(d[i]) - 1
                if a < b:
                    print(0)
                    break
                children |= d[i]
                if b == 0:
                    continue
                ans *= perm(a, b)
            else:
                for i in history:
                    if i in children:
                        children.remove(i)
                if len(children) == 0:
                    print(ans % mod)
                    break
                history, root = root, children
                continue
            break

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)