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

import sys
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]

if len(set(A))<len(A) or len(set(B))<len(B):
    print(0)
    sys.exit()

else:
    
    ans = 1
    rows, columna = 0,0
    mod = 10**9+7
    for x in range(N*M, 0, -1):
        in_A = x in A
        in_B = x in B

        if in_A and in_B:
            rows += 1
            columna += 1

        elif in_A:
            rows += 1
            ans *= columna

        elif in_B:
            columna += 1
            ans *=rows

        else:
            ans *= (rows * columna -(N*M-x))

        ans %= mod

    print(ans%mod)


### FIXED CODE ###

def solve():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = set(map(int, input().split()))
    B = set(map(int, input().split()))
    
    row, columun = 0, 0
    ans = 1
    for i in range(N * M, 0, -1):
        in_A = i in A
        in_B = i in B
        if in_A and in_B:
            row += 1
            columun += 1
        elif in_A:
            row += 1
            ans *= columun
        elif in_B:
            columun += 1
            ans *= row
        else:
            ans *= row * columun - (N * M - i)
        ans %= MOD
    print(ans)


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

N = int(input())

d = {}

for i in range(N):
    s = input()
    if s in d:
        d[s] = d[s] + 1
    else:
        d[s] = 1


max_kv_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
max_kv_list = sorted(max_kv_list)
for ans in max_kv_list:
    print(ans)

### FIXED CODE ###

N = int(input())

d = {}

for i in range(N):
    s = input()
    if s in d:
        d[s] = d[s] + 1
    else:
        d[s] = 1

hoge = max(d.values())

max_kv_list = [kv[0] for kv in d.items() if kv[1] == hoge]

max_kv_list = sorted(max_kv_list)
for ans in max_kv_list:
    print(ans)
### BUGGY CODE ###

n,k,q = map(int,input().split())
a = [int(input()) for i in range(q)]
p = [k] * n
for t in range(q):
    for j in range(0,n):
        if j == a[t]-1:
            pass
        else:
            p[j]-=1
for r in p:
    if r <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

n,k,q = map(int,input().split())
a = [int(input()) for i in range(q)]
p = [k-q] * n

for j in range(q):
    p[a[j]-1]+=1

for r in p:
    if r >= 1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [0]
for i in range(1, n):
    dp += [min([dp[-j] + abs(h[i] - h[i - j]) for j in range(1, min(i, k) + 1)])]
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [0]
for i in range(1, n):
    to = min(i, k) + 1
    dp += [min([dp[-j] + abs(h[i] - h[i - j]) for j in range(1, to)])]
print(dp[-1])
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
goukei = []
for i in range(x):
    for j in range(y):
        goukei.append(A[i] + B[j])
goukei.sort()
goukei2 = goukei[-k:]
goukei3 = []
for c in C:
    for ab in goukei2:
        goukei3.append(ab + c)
goukei3.sort(reverse=True)
print(*goukei3[:k], sep="\n")


### FIXED CODE ###

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
goukei = []
for a in A:
    for b in B:
        goukei.append(a + b)
goukei.sort()
goukei2 = goukei[-k:]
goukei3 = []
for c in C:
    for ab in goukei2:
        goukei3.append(ab + c)
goukei3.sort(reverse=True)
print(*goukei3[:k], sep="\n")
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
num = [0 for i in range(N)]
zu = []
ans = []
for i in A:
    num[i-1]+=1
sums = 0
for i in range(N):
    temp = 1/2*num[i]*(num[i]-1)
    zu.append(int(temp))
for i in A:
    num[i-1]-=1
    temp = zu[i-1]
    zu[i-1] = 1/2*num[i-1]*(num[i-1]-1)
    ans.append(int(sum(zu)))
    zu[i-1] = temp
    num[i-1]+=1

for i in range(N):
    print(ans[i])

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
num = [0 for i in range(N)]
zu = 0
ans = []
for i in A:
    num[i-1]+=1
for i in range(N):
    temp = 1/2*num[i]*(num[i]-1)
    zu += temp
for i in A:
    kawari =zu
    temp1 = 1/2*num[i-1]*(num[i-1]-1)
    num[i-1] -= 1
    temp2 = 1/2*num[i-1]*(num[i-1]-1)
    kawari += -temp1+temp2
    num[i-1] += 1
    print(int(kawari))
### BUGGY CODE ###

n=int(input())
ans=0
for i in range(n):
    a=0
    while int(i%2)==0:
        a+=1
        i=i//2
    ans=max(ans,a)
print(ans)

### FIXED CODE ###

n=int(input())
l=[2**i for i in range(8)]
for i in l[::-1]:
    if i<=n:
        print(i)
        break
### BUGGY CODE ###

def judge(n, k, a_list_s, f_list_s, v):
    res = 0
    # print(v)
    for i in range(n):
        a_necessary = v // f_list_s[i]
        # print(a_necessary, a_list_s[i])
        if a_list_s[i] > a_necessary:
            res += a_list_s[i] - a_necessary
    if res > k:
        return False
    else:
        return True


def solve_e(n, k, a_list, f_list):

    if sum(a_list) <= k:
        return 0
    
    a_list_s = sorted(a_list)
    f_list_s = sorted(f_list, reverse=True)

    left = 0
    right = 10 ** 12

    while right - left > 1:
        middle = (left + right) // 2
        if judge(n, k, a_list_s, f_list_s, middle):
            right = middle
        else:
            left = middle
    return right


def main():
    # input
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    f_list = list(map(int, input().split()))
    res = solve_e(n, k, a_list, f_list)
    print(res)


def test():
    assert solve_e(3, 5, [4, 2, 1], [2, 3, 1]) == 2
    assert solve_e(3, 8, [4, 2, 1], [2, 3, 1]) == 0
    assert solve_e(
        11, 14, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5],
        [8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2]) == 12


if __name__ == "__main__":
    test()
    main()


### FIXED CODE ###

def judge(n, k, a_list_s, f_list_s, v):
    res = 0
    # print(v)
    for i in range(n):
        a_necessary = v // f_list_s[i]
        # print(a_necessary, a_list_s[i])
        if a_list_s[i] > a_necessary:
            res += a_list_s[i] - a_necessary
    if res > k:
        return False
    else:
        return True


def solve_e(n, k, a_list, f_list):

    if sum(a_list) <= k:
        return 0
    
    a_list_s = sorted(a_list)
    f_list_s = sorted(f_list, reverse=True)

    left = 0
    right = 10 ** 12

    while right - left > 1:
        middle = (left + right) // 2
        if judge(n, k, a_list_s, f_list_s, middle):
            right = middle
        else:
            left = middle
    return right


def main():
    # input
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    f_list = list(map(int, input().split()))
    res = solve_e(n, k, a_list, f_list)
    print(res)


def test():
    assert solve_e(3, 5, [4, 2, 1], [2, 3, 1]) == 2
    assert solve_e(3, 8, [4, 2, 1], [2, 3, 1]) == 0
    assert solve_e(
        11, 14, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5],
        [8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2]) == 12


if __name__ == "__main__":
    test()
    main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
#A=[1,1,1,1,1,1,1]
#N=7
A.sort(reverse=True)
L=[]
dis=[A[0]]
L.append(A[0])
L.append(A[0])
#print(L)
num=0
for i in range(1,len(A)):
    ind=dis.index(max(dis))
    num+=dis.pop(ind)
    #L.insert(ind+1,A[i])
   
    dis.append(A[i])
    dis.append(A[i])
print(num)
#print(L)
#print(dis)

### FIXED CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))
#A=[1,1,1,1,1,1,1]
#N=7
A.sort(reverse=True)
dis=deque([A[0]])
num=0
for i in range(1,len(A)):
    num+=dis.popleft()
    #L.insert(ind+1,A[i])
    dis.append(A[i])
    dis.append(A[i])
print(num)
#print(L)
#print(dis)
### BUGGY CODE ###

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

E = []

for i in range(N):
    E.append((P[i]+1)/2)

l = N - K + 1
tnt = 0
ans = 0
j = 0
k = K

while k <= N:
    tnt = sum(E[j:k])
    ans = max(ans, tnt)
    j += 1
    k += 1

print(ans)


### FIXED CODE ###

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

E = []

for i in range(N):
    E.append((P[i]+1)/2)

tnt = sum(E[:K])
ans = tnt

for i in range(N-K):
    tnt = tnt + E[K+i] - E[i]
    ans = max(ans, tnt)

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

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

H, W = reads()
S = []
for _ in range(H):
  S.append(input())

N = H + W
field = [[0] * N for _ in range(N)]
for i in range(H):
  for j in range(W):
    field[i+j][i-j+W] = int(S[i][j] == '#')

accRow = [None] * N
for i in range(N):
  accRow[i] = [0] + list(accumulate(field[i][j] for j in range(N)))

accCol = [None] * N
for i in range(N):
  accCol[i] = [0] + list(accumulate(field[j][i] for j in range(N)))

ans = 0
for i in range(N):
  for j in range(N):
    for k in range(j+1, N):
      d = k - j
      if field[i][j] == field[i][k] == 1:
        if i - d >= 0:
          ans += accRow[i-d][k+1] - accRow[i-d][j]
        if i + d < N:
          ans += accRow[i+d][k+1] - accRow[i+d][j]
      if field[j][i] == field[k][i] == 1:
        if i - d >= 0:
          ans += accCol[i-d][k+1] - accCol[i-d][j]
        if i + d < N:
          ans += accCol[i+d][k+1] - accCol[i+d][j]

for i in range(N):
  for j in range(N):
    if field[i][j] != 1:
      continue
    for d in range(1, N):
      if i + d < N and j + d < N and field[i][j+d] == field[i+d][j] == 1:
        ans -= 1
      if i + d < N and j - d >= 0 and field[i][j-d] == field[i+d][j] == 1:
        ans -= 1
      if i - d >= 0 and j - d >= 0 and field[i][j-d] == field[i-d][j] == 1:
        ans -= 1
      if i - d >= 0 and j + d < N and field[i][j+d] == field[i-d][j] == 1:
        ans -= 1

print(ans)

### FIXED CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

H, W = reads()
S = []
for _ in range(H):
  S.append(input())

N = H + W
field = [[0] * N for _ in range(N)]
for i in range(H):
  for j in range(W):
    field[i+j][i-j+W] = int(S[i][j] == '#')

accRow = [None] * N
for i in range(N):
  accRow[i] = [0] + list(accumulate(field[i][j] for j in range(N)))

accCol = [None] * N
for i in range(N):
  accCol[i] = [0] + list(accumulate(field[j][i] for j in range(N)))

# for f in field:
#   print(f)

ans = 0
for i in range(N):
  for j in range((i+W)%2, N, 2):
    for k in range(j+2, N, 2):
      d = k - j
      if field[i][j] == field[i][k] == 1:
        if i - d >= 0:
          ans += accRow[i-d][k+1] - accRow[i-d][j]
        if i + d < N:
          ans += accRow[i+d][k+1] - accRow[i+d][j]
      if field[j][i] == field[k][i] == 1:
        if i - d >= 0:
          ans += accCol[i-d][k] - accCol[i-d][j+1]
        if i + d < N:
          ans += accCol[i+d][k] - accCol[i+d][j+1]

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

import math
from functools import reduce


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


def main():
    N = int(input())
    A = list(map(int, input().split()))

    tmp = [0] * N

    s = 1
    for i in range(N):
        tmp[- i - 1] = s
        s = lcm(s, A[-i - 1])

    is_pairwise_coprime = True
    for i in range(N - 1):
        if math.gcd(A[i], tmp[i]) != 1:
            is_pairwise_coprime = False

    gcd_ = reduce(math.gcd, A)

    if is_pairwise_coprime:
        print('pairwise coprime')
    elif gcd_ == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
from functools import reduce
from collections import defaultdict


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A_max = max(A)

    is_pairwise_coprime = True

    D = [-1] * (A_max + 1)
    for i in range(2, A_max + 1):
        if D[i] == -1:
            D[i] = i
            for j in range(i*i, A_max+1, i):
                D[j] = i

    def factorization(n):
        # assert 0 < n <= A_max
        primes_ = defaultdict(int)
        temp = n
        while temp > 1:
            primes_[D[temp]] += 1
            temp = temp // D[temp]

        return primes_

    P = [False]*(A_max+1)

    # primes = set({})
    for i in range(N):
        for p in factorization(A[i]).keys():
            # if p in primes:
            if P[p]:
                is_pairwise_coprime = False
                break
            else:
                # primes.add(p)
                P[p] = True

    gcd_ = reduce(math.gcd, A)

    if is_pairwise_coprime:
        print('pairwise coprime')
    elif gcd_ == 1:
        print('setwise coprime')
    else:
        print('not coprime')


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

n, d, a = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(n)])

l = [0]*(n+1)
ans = 0
for i in range(n):
    if xh[i][1] <= 0:
        continue 
    c = -(-xh[i][1]//a)
    ans += c
    for j in range(i+1, n):
        if xh[j][0] <= xh[i][0] + d*2:
            xh[j][1] -= c*a
        else:
            break
print(ans)

### FIXED CODE ###

from collections import deque

n, d, a = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(n)])

ans = 0
dam_sum = 0
q = deque()
for i, (x, h) in enumerate(xh):
    while q and q[0][0] < x:
        ran, dam = q.popleft()
        dam_sum -= dam
    h -= dam_sum
    if h <= 0:
        continue 
    c = -(-h//a)
    ans += c
    dam_sum += c*a
    q.append((x+d*2, c*a))
print(ans)
### BUGGY CODE ###

l,r=[int(i) for i in input().split()]
ans=2018
for i in range(l,r):
    for j in range(i+1,r+1):
        ans=min(i*j%2019,ans)
        if ans==0:
            break
print(ans)

### FIXED CODE ###

l,r=[int(i) for i in input().split()]
ans=2018
for i in range(l,r):
    for j in range(i+1,r+1):
        ans=min(i*j%2019,ans)
        if ans==0:
            print(ans)
            exit()
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

k = int(input())

keta = 4

ans_c = []
sunuke = []
for i in range(1, 10**keta):  # 1~9999
    a = i
    b = sum([int(j) for j in str(i)])
    tmp_sunuke = a/b
    ans_c.append(a)
    sunuke.append(tmp_sunuke)

base = 10
nines = 9
while(len(ans_c) <= 9000000):
    for i in range(1000, 10**keta):  # 1000~9999
        a = i*base+nines
        b = sum([int(j) for j in str(i)])
        tmp_sunuke = a/b
        ans_c.append(a)
        sunuke.append(tmp_sunuke)
    base *= 10
    nines = nines*10 + 9
    # print(len(ans_c))

# print(ans_c)

tmp = 10**10
ans = []
for i in reversed(range(len(ans_c))):
    if sunuke[i] <= tmp:
        tmp = sunuke[i]
        ans.append(ans_c[i])
# print(ans)


for i in range(0, k):
    print(ans[-1-i])


### FIXED CODE ###

#!/usr/bin/env python3

k = int(input())

now = 1
step = 1


def sunuke(n):
    r = 0
    while n:
        r += n % 10
        n //= 10
    return r


def ok(a, b):
    return a * sunuke(b) <= b*sunuke(a)


while k:
    if ok(now, now+step):
        print(now)
        k -= 1
        now += step
    else:
        nstep = step*10
        while now % nstep != nstep-1:
            now += step
        step = nstep
### BUGGY CODE ###

# -*- coding: utf-8 -*-
H, N = map(int, input().split(' '))
nums = [float('inf') for _ in range(H+1)]
nums[0] = 0

for _ in range(N):
    a, b = map(int, input().split(' '))
    for i in range(H + 1):
        j = min(H, i+a)
        nums[j] = min(nums[j], nums[i] + b)

print(nums[H])

### FIXED CODE ###

# -*- coding: utf-8 -*-
H, N = map(int, input().split(' '))

lim = float('inf')
powers = [lim for _ in range(H+1)]
powers[0] = 0

for _ in range(N):
    A, B = map(int, input().split(' '))
    for i in range(H):
        if powers[i] != lim:
            if i+A > H:
                powers[H] = min(powers[H], powers[i] + B)
            else:
                powers[i+A] = min(powers[i+A], powers[i] + B)


# print(powers)
print(powers[H])
### BUGGY CODE ###

from bisect import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0
for i in A:
    min_B = bisect(B, i)
    # print("min_B", min_B)
    for j in range(min_B, len(B)):
        min_C = bisect(C, B[j])
        # print("min_C", min_C)
        ans += len(C) - min_C
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):
    upper = bisect.bisect_left(A, B[i])
    downer = bisect.bisect_right(C, B[i])
    ans += upper*(len(C)-downer)
print(ans)
### BUGGY CODE ###

N = int(input())
a = map(int,input().split())
b = list(a)
for i in range(N):
    print(b.count(i+1))


### FIXED CODE ###

N = int(input())
a = map(int,input().split())
b = list(a)
c = [0]*N
for i in range(N-1):
    c[b[i]-1] += 1
for j in range(N):
    print(c[j])
### BUGGY CODE ###


s=list(input())
l=len(s)
mod=10**9+7
dp=[0]*13
dp[0] = 1
mul=1
for i in s[::-1]:
    nextDp=[0]*13
    if i=="?":
        for k in range(10):
            for j in range(13):
                nextDp[(k*mul+j)%13] += dp[j]
                #nextDp[(k*mul+j)%13]%=mod
    else:
        for j in range(13):
            nextDp[(int(i)*mul+j)%13] += dp[j]
            #nextDp[(int(i)*mul+j)%13]%=mod
    mul *= 10
    dp = nextDp

print(dp[5]%mod)

### FIXED CODE ###

MOD = 10**9 + 7
S = input()
 
cur = [0] * 13
cur[0] = 1
r = 1
base = 0
for i in range(len(S)):
    s = S[-(i+1)]
    if s == '?':
        prev = cur
        cur = [sum(prev)] * 13
        for m in range(13):
            for d in range(10,13):
                cur[(m + r*d) % 13] -= prev[m]
        for m in range(13):
            cur[m] %= MOD
    else:
        base = (base + r*int(s)) % 13
 
    r = (10 * r) % 13
 
print(cur[(5-base) % 13])
### BUGGY CODE ###

mod = 10**9+7
n = int(input())
s = input()
dic = [0 for _ in range(26)]
for i in range(n):
    dic[ord(s[i])-97] += 1
dic = [i for i in dic if i > 0]
result = 0
for i in range(1, 2**len(dic)):
    c = 1
    n = []
    num = i
    for j in dic:
        if num%2==1:
            c *= j
            c %= mod
            n.append(j)
        else:
            n.append(0)
        num >>= 1
    result += c
    result %= mod

print(result%mod)

### FIXED CODE ###

mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in s:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
result = 1
for i, j in d.items():
    result = (result*(j+1))%mod

print((result-1)%mod)
### BUGGY CODE ###

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

answer = 0
mod = 1000000007
for i in range(N-1):
  for j in range(i+1, N):
    answer += (A[i] * A[j]) % mod
    answer %= mod
print(int(answer))

### FIXED CODE ###

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

answer = 0
a_sum = sum(A)
mod = 10**9+7

for i in range(N-1):
  a_sum -= A[i]
  answer += a_sum * A[i]
print(str(answer % mod))
### BUGGY CODE ###

s=input()
l=len(s)
mod = pow(10,9)+7

dp = [[0 for _ in range(13)] for _ in range(l+1)]
dp[0][0] = 1
keta = 1

for i in range(1,l+1):
	num = s[-i]
	if num == '?':
		for j in range(10):
			for k in range(13):
				dp[i][(j * keta + k) % 13] += dp[i-1][k] % mod
	else:
		num = int(num)
		for k in range(13):
			dp[i][(num * keta + k) % 13] += dp[i-1][k] % mod
	keta = keta*10  % 13
print(dp[l][5] % mod)

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

s=input()[::-1]
p=["maerd","remaerd","resare","esare"]
while True:
  if s[:5]==p[0]:s=s.replace(p[0],"",1)
  elif s[:5]==p[3]:s=s.replace(p[3],"",1)
  elif s[:7]==p[1]:s=s.replace(p[1],"",1)
  elif s[:6]==p[2]:s=s.replace(p[2],"",1)
  else:
    if s=="":print("YES");break
    else:print("NO");break


### FIXED CODE ###

s=input()[::-1]
p=["maerd","remaerd","resare","esare"]
while True:
  if s[:5]==p[0]:s=s[5:]
  elif s[:5]==p[3]:s=s[5:]
  elif s[:7]==p[1]:s=s[7:]
  elif s[:6]==p[2]:s=s[6:]
  else:
    if s=="":print("YES");break
    else:print("NO");break
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


N, K = list(map(int, input().split()))
ab = []
for i in range(N-1):
    ab.append(list(map(int, input().split())))

ki = []

for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []

for i in range(N-1):
    ki[ab[i][0] - 1]["eda"].append([ab[i][1] - 1])
    ki[ab[i][1] - 1]["eda"].append([ab[i][0] - 1])

def P(m ,n):
    if m <= 0 or n <= 0:
        return 0
    else:
        num = 1
        for i in range(n):
            num *= m-i
        return num

def saiki(i, base, ki):
    num = 1
    eda_num = len(ki[i]["eda"])-1
    if eda_num == 0:
        return num
    num *= P(K-2, eda_num)

    for edge in ki[i]["eda"]:
        if edge[0] != base:
            num *= saiki(edge[0], i, ki)

    num = num % 1000000007
    return num

total_num = K
if len(ki[0]["eda"]) != 0:
    total_num *= P(K-1, len(ki[0]["eda"]))
    for edge in ki[0]["eda"]:
        total_num *= saiki(edge[0], 0, ki)
        total_num = total_num % 1000000007
        if total_num == 0:
            break

print(total_num)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()