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

n = int(input())
a = [sorted(input()) for i in range(n)]

ans = 0
for i in range(n):
    for j in range(n):
        if i!=j:
            if a[i] == a[j]:
                ans +=1
print(ans//2)

### FIXED CODE ###

import itertools
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a = [sorted(input()) for i in range(n)]
l = []
for i in a:
    l.append("".join(i))

ans = 0
dic = {}

for i in range(n):
    if l[i] in dic:
        dic[l[i]] +=1
    else:
        dic[l[i]] =1

for i in dic.values():
    if i>=2:
        ans += combinations_count(i, 2)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split())) + [0]*100010

dp = [float("inf")]*100010
dp[0] = 0

for i in range(N):
    for k in range(1, K+1):
        dp[i+k] = min(dp[i+k], dp[i] + abs(h[i+k] - h[i]))
    # print(dp)
print(dp[N-1])

### FIXED CODE ###

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

dp = [float("inf") for i in range(n)]
dp[0] = 0
for i in range(n-1):
    for j in range(1, min(k+1, n-i)):
        dp[i+j] = min(dp[i+j], dp[i]+abs(a[i+j]-a[i]))

print(dp[-1])
### BUGGY CODE ###

import itertools
 
s = str(input())
 
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
 
M = 1
INF = 10 ** 9 + 7
      
for i in range(n):
  if s[n-1-i] == '?':
    for k, j in itertools.product(range(10), range(13)):
      x = (j+k*10**i)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  else:
    for j in range(13):
      x = (j+int(s[n-1-i])*10**i)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  #M = (M*10)%13

print(dp[-1][5])
#print(dp[-1][5]%(10**9+7))
#print(dp)

### FIXED CODE ###

import itertools
 
s = str(input())
 
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1

M = 1
INF = 10 ** 9 + 7
      
for i in range(n):
  if s[n-1-i] == '?':
    for k, j in itertools.product(range(10), range(13)):
      x = (j+k*M)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  else:
    for j in range(13):
      x = (j+int(s[n-1-i])*M)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  M = (M*10)%13

print(dp[-1][5])
#print(dp[-1][5]%(10**9+7))
#print(dp)
### BUGGY CODE ###

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

for i in range(1, n + 1):
    count = a.count(i)
    print(count)



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
lst = [0] * n
for i in a:
    lst[i-1] += 1
print(*lst)
### BUGGY CODE ###

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

for i in range(N):
    print(A.count(i+1))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
num = [0 for i in range(N)]
for i in A:
    num[i-1] += 1
for l in num:
    print(l)
### BUGGY CODE ###

n,x = map(int, input().split())
l = [ abs(i - x) for i in list(map(int, input().split()))]
l.sort(reverse=True)
if len(l) == 1:ans = l[0]
else:
  while len(l) != 1:
    l.sort(reverse=True)
    l.append(0)
    l = [ l[i] - l[i+1] for i in range(len(l) - 1)]
    l = list(set(l))
  ans = l[0]
print(ans)

### FIXED CODE ###

n,x = map(int, input().split())
l = [ abs(i - x) for i in list(map(int, input().split()))]
l.sort(reverse=True)
l = list(set(l))
if len(l) == 1:ans = l[0]
else:
  while len(l) != 1:
    l.sort(reverse=True)
    l.append(0)
    l = [ l[i] - l[i+1] for i in range(len(l) - 1)]
    l = list(set(l))
    for i in l:
      if i % min(l) != 0:break
    else:
      l[0] = min(l)
      break
  ans = l[0]
print(ans)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache
sys.setrecursionlimit(10**6)
@lru_cache(maxsize=None)
def rec(v):
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global dp,graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    dp=[-1]*n #頂点i(0-)を始点としたときの有効パスの長さの最大値
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
def rec(v):
    if dp[v]!=-1:return dp[v]
    res=0
    for nv in graph[v]:
        res=max(res,rec(nv)+1)
    dp[v]=res
    return res
def main():
    n,m=map(int,input().split())
    XY=[tuple(map(int,input().split())) for i in range(m)]
    global dp,graph
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
    dp=[-1]*n #頂点i(0-)を始点としたときの有効パスの長さの最大値
    ans=0
    for v in range(n):
        ans=max(ans,rec(v))
    print(ans)

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

n,y = list(map(int,input().split()))
if y/10000 > n:
    print('-1 -1 -1')
if y/10000 ==n:
    print('%d %d %d' % (y/10000, 0, 0))
else:
    b = False
    YY =[]
    Y10=int(y/10000)
    Y5 =int(y/5000)
    Y1 =int(y/1000)
    for i in range(Y10,-1,-1):
        if b== True or i > n:
            break
        for j in range(Y5+1-2*i):
            if b == True or i+j > n:
                break
            for k in range(Y1+1-10*i):
                if i+j+k == n and i*10000+j*5000+k*1000 ==y:
                    YY = [i,j,k]
                    print('%d %d %d' % (YY[0], YY[1], YY[2]))
                    b = True
                    break
                else:
                    YY=[]
        if i == 0 and b == False:
            print('-1 -1 -1')

### FIXED CODE ###

n,y = list(map(int,input().split()))
if y/10000 > n:
    print('-1 -1 -1')
if y/10000 ==n:
    print('%d %d %d' % (y/10000, 0, 0))
else:
    b = False
    YY =[]
    Y10=int(y/10000)
    Y5 =int(y/5000)
    Y1 =int(y/1000)
    for i in range(Y10,-1,-1):
        if b== True or i > n:
            break
        for j in range(Y5+1-2*i):
            if b == True or i+j > n:
                break
            k = n - i - j
            if i*10000+j*5000+k*1000 ==y:
                YY = [i,j,k]
                print('%d %d %d' % (YY[0], YY[1], YY[2]))
                b = True
                break
            else:
                YY=[]
        if i == 0 and b == False:
            print('-1 -1 -1')
### BUGGY CODE ###

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

a_set = list(set(a))
if len(a_set) < K:
    print(0)
    exit()

num_dict = {}
for num in a_set:
    num_dict[num] = a.count(num)
num_dict = sorted(num_dict.items(), key = lambda x: x[1])

diff = len(a_set) - K
ans = 0
for i in range(diff):
    ans += num_dict[i][1]
print(ans)


### FIXED CODE ###

from collections import Counter

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

sum = 0
c = Counter(a).most_common()
if K > len(c):
    print(0)
    exit()
for i in range(K):
    sum += c[i][1]
print(len(a) - sum)
### BUGGY CODE ###

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

minlist=[]
for n in range(N):
    if n==0:
        minlist.append(1)
    elif P[n]==min(P[:n+1]):
        minlist.append(1)
    else:
        pass
print(sum(minlist))

### FIXED CODE ###

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

min=1000000000
minnum=[]
for n in range(N):
	if P[n]<=min:
		minnum.append(1)
		min=P[n]
print(sum(minnum))
### BUGGY CODE ###

n,m=map(int,input().split())
s=[]
for i in range(m):
  d=list(map(int,input().split()))
  s.append(d)
for j in range(m-1):
  for k in range(j+1,m):
    if (s[j][0]==1 and s[j][1]==s[k][0] and s[k][1]==n) or (s[k][0]==1 and s[k][1]==s[j][0] and s[j][1]==n):
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")


### FIXED CODE ###

n,m=map(int,input().split())
s=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  s[a-1].append(b)
for j in s[0]:
  if n in s[j-1]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

def attack(A):
  A = list(set(A))
  A.sort()
  if A[0] ==0:
    A.pop(0)
  attack_mons = A[0]
  new_A = [A[0]]
  for i in range(1,len(A)):
    new_A.append(A[i]%min(A))
  return new_A

new_A = attack(A)
while A!=new_A:
  A = new_A
  new_A = attack(new_A)

print(min(new_A))


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

ans = A[0]

for a in A:
  ans = gcd(ans,a)

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

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A2=sorted(A)
B2=sorted(B)
C2=sorted(C)
ans = 0
sum = 0
t =0
b = 0
for i in range(N):
    a = A2[i]
    low = 0
    high = N-1
    while True:
        t = (low + high) // 2
        if B2[t] <= a:
            if t == N-1:
                b = False
                break
            elif B2[t] <= a <B2[t+1]:
                b = B2[t+1]
                t = t + 1
                break
            else:
                low = t+1
                continue
        elif B2[t] > a:
            if t == 0:
                b = B2[0]
                break
            elif B2[t] > a >= B2[t-1]:
                b = B2[t]
                break
            else:
                high = t - 1
                continue
    if b != False:
        for j in range(t,N):
            b = B2[j]
            low = 0
            high = N - 1
            while True:
                #print(a, b)
                t = (low + high) // 2
                if C2[t] <= b:
                    if t == N-1:
                        ans = 0
                        break
                    elif C2[t] <= b < C2[t + 1]:
                        c = C2[t + 1]
                        ans = N - t - 1
                        break
                    else:
                        low = t + 1
                        continue
                elif C2[t] > b:
                    if t == 0:
                        ans = N
                        break
                    elif C2[t] > b >= C2[t - 1]:
                        c = C2[t]
                        ans = N - t
                        break
                    else:
                        high = t - 1
                        continue
                #print("ans={}".format(ans))
            sum += ans

print(sum)


### FIXED CODE ###

N = int(input())
A = list(int(i) for i in input().split())
B = list(int(i) for i in input().split())
C = list(int(i) for i in input().split())
A.sort()
B.sort()
C.sort()
sum = 0
for j in range(N):
    low = low2 = 0
    high = high2 = N
    b = B[j]
    mid = mid2 = 0
    #print(b)
    while(high>low):
        mid = (high + low)//2
        if b > A[mid]:
            low = mid +1
        else:
            high = mid
    acount = low
    while (high2>low2):
        mid2 = (high2 + low2)//2
        if b < C[mid2]:
            high2 = mid2
        else:
            low2 = mid2 + 1
    ccount=N-low2
    sum += acount*ccount
print(sum)
### BUGGY CODE ###

s = input()
q = int(input())
direction = 1
mae = ""
usiro = ""
for i in range(q):
    # print(i)
    qi = input()
    if qi == "1":
        direction *= -1
        # print(123, direction)
    else:
        tfq = list(qi.split())
        # print(tfq)
        t = tfq[0]
        f = tfq[1]
        q = tfq[2]

        if f == "1":
            if direction == 1:
                mae += q
            else:
                usiro += q
        else:
            if direction == 1:
                usiro += q
            else:
                mae += q
    # print(i, direction)

if direction == -1:
    s = usiro[::-1] + s[::-1] + mae
else:
    s = mae[::-1] + s + usiro
print(s)

### FIXED CODE ###

s = list(input())
q = int(input())
direction = 1
mae = []
usiro = []
for i in range(q):
    qi = input()
    if qi == "1":
        direction *= -1
    else:
        tfq = list(qi.split())
        t = tfq[0]
        f = tfq[1]
        q = tfq[2]

        if f == "1":
            if direction == 1:
                mae.append(q)
            else:
                s.append(q)
        else:
            if direction == 1:
                s.append(q)
            else:
                mae.append(q)
# print(mae)
if direction == -1:
    for i in s[::-1]:
        print(i, end = "")
    for i in mae:
        print(i, end = "")
else:
    for i in mae[::-1]:
        print(i, end = "")
    for i in s:
        print(i, end = "")
### BUGGY CODE ###

S = str(input())
li = [0]*2019
ans = 0

for i in range(len(S)):
  s = int(S[i:]) % 2019
  if s == 0:
    ans += 1
  else:
    li[s] += 1
  
for l in li:
  if l > 1:
    ans += l*(l-1)//2

print(ans)

### FIXED CODE ###

S = str(input())
li = [0] * 2019
ans = 0
li[0] = 1

d = 1
s = 0
for i in S[::-1]:
  s += int(i) * d
  s = s % 2019
  li[s] += 1
  d *= 10
  d = d % 2019
  
for l in li:
  ans += l * (l-1) // 2

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

# -*- coding: utf-8 -*-
 
X = int(input())

A_max = 0
abs_X = abs(X)
cnt = 0

while 1:
  if ( cnt**5 >= abs_X ):
    cnt += 1
    A_max = i
    break

print(A_max)
B_max = A_max

for i in range(0, A_max+1):
  for j in range(0, B_max+1):
    
    A = i**5
    B = j**5
    
    if ( A+B==X or A-B==X or -A+B==X or -A-B==X ):
      print(i,j)
      break
  
  else:
    continue
  break


### FIXED CODE ###

# -*- coding: utf-8 -*-
 
X = int(input())

AB_max = 0
abs_X = abs(X)

for i in range(10**9):
  if ( i**5-(i-1)**5 > 10**9 ):
    AB_max = i
    break

#print(AB_max)

for i in range(AB_max+1):
  for j in range(AB_max+1):
    
    A = i**5
    B = j**5
    
    if ( A-B==X ):
      print(i,j)
      break
    elif ( A-(-B)==X ):
      print(i,-j)
      break
    elif ( (-A)-B==X ):
      print(-i,j)
      break
    elif ( (-A)-(-B)==X ):
      print(-i,-j)
      break
      
  else:
    continue
  break
### BUGGY CODE ###

x = int(input())

for i in range(int(x**(3/5)+1)):
    for j in range(-int((x)**(1/5))-1,int((x)**(1/5))+1):
        if i**5 - j**5 == x:
            print(i,j)
            break
    else:
        continue
    break


### FIXED CODE ###

x = int(input())

for i in range(-200,200):
    for j in range(-200,200):
        if i**5 - j**5 == x:
            print(i,j)
            exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    s = sorted(list(map(int, input().strip().split())), reverse=True)
    check = [False] * (2**N)
    now = []
    now.append([s[0], 1])
    check[0] = True
    ok = True
    for i in range(N):
        next_ = []
        for j in range(len(now)):
            hp, start = now[j]
            ok = False
            for k in range(start, 2**N):
                if s[k] < hp and not check[k]:
                    check[k] = True
                    next_.append([s[k], k+1])
                    ok = True
                    break
            if not ok:
                break
        now += next_
        if not ok:
            break
    
    if ok:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    s = sorted(list(map(int, input().strip().split())), reverse=True)
    check = [False] * (2**N)
    now = []
    now.append([s[0], 1])
    check[0] = True
    ok = True
    for i in range(N):
        next_ = []
        tmp = 0
        for j in range(len(now)):
            hp, start = now[j]
            start = max(start, tmp)
            ok = False
            for k in range(start, 2**N):
                if s[k] < hp and not check[k]:
                    tmp = k+1
                    now[j][1] = k+1
                    check[k] = True
                    next_.append([s[k], k+1])
                    ok = True
                    break
            if not ok:
                break
        now += next_
        now = sorted(now, reverse=True)
        if not ok:
            break
    
    if ok:
        print("Yes")
    else:
        print("No")

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


N, K = map(int, input().split())
S = input()
S = S + "8"

a = []
f = S[0]
l = 0
for i in range(1, N+1):
    #print(S[i])
    if f != S[i]:
        #a.append([l, i-1, int(f)])
        #a.append([i-l, int(f)])
        a.append(i-l)
        l = i
        f = S[i]
        
#print(a)

if S[0] == '0':
    a = [0] + a

MAX = 0
for i in range(len(a)):
    if i % 2 == 0:
        #print(a[i:i+2*K+1])
        #print(sum(a[i:i+2*K+1]))
        MAX = max(MAX, sum(a[i:i+2*K+1]))

print(MAX)

### FIXED CODE ###


N, K = map(int, input().split())
S = input()
S = S + "8"

a = []
f = S[0]
l = 0
for i in range(1, N+1):
    if f != S[i]:
        a.append(i-l)
        l = i
        f = S[i]
        

if S[0] == '0':
    a = [0] + a

SUM = sum(a[0:0+2*K+1])

MAX = max(0, SUM)
for i in range(2, len(a)):
    if i % 2 == 0:
        try:
            SUM = SUM - (a[i-2]+a[i-1]) + (a[i+2*K-1]+a[i+2*K])
        except:
            try:
                SUM = SUM - (a[i-2]+a[i-1]) + (a[i+2*K-1])
            except:
                break
        
        MAX = max(MAX, SUM)


print(MAX)
### BUGGY CODE ###

import bisect

N, M = map(int, input().split())

A = list(map(int, input().split()))
A.sort()
#print(A)

for _ in range(M):
    a = A.pop()/2
    bisect.insort_left(A, a)

print(sum(list(map(int, A))))

### FIXED CODE ###

import heapq #今回は優先度キューを使う

N, M = map(int, input().split())

A = list(map(lambda x:-int(x), input().split())) #優先度付きキューは最小値しか出せないので、×-1して最大値を最小値にしている
#A.sort() 今回は間に合わない
heapq.heapify(A) #優先度付きキューに変換
#print(A)

for _ in range(M):
    a = heapq.heappop(A) #最小値取得
    a = -a // 2 #負のまま計算すると切り捨てが違うところで起こる
    heapq.heappush(A,-a) #優先度付きキューに挿入

print(-sum(A))
### BUGGY CODE ###

import numpy as np

num_q = int(input())
x = 0
f = 0
a = []
c = False
b = 0

for _ in range(num_q):
  q = input()
  if q[0] == '2':
    print(x, f)
  else:
    _, n, m = map(int, q.split(" "))
    a.append(n)
    a.sort()
    x_tmp = a[b//2]
    if c:
      f += m + np.abs(x - n)
    else:
      f += m + np.abs(x_tmp - n)
    c = ~c
    x = x_tmp
    b += 1


### FIXED CODE ###

from heapq import heappush, heappop

num_q = int(input())
x = 0
f = 0
low = []
high = []
odd = False
num_a = 0
 
for _ in range(num_q):
  q = input()
  if q[0] == '2':
    print(x, f)
  else:
    _, n, m = map(int, q.split(" "))
    if odd:
      if n >= -low[0]:
        f += m + n + low[0]
        heappush(high, n)
      else:
        f += m - n - low[0]
        heappush(low, -n)
        heappush(high, -heappop(low))
    else:
      f += m
      if num_a == 0:
        heappush(low, -n)
      else:
        if n > -low[0]:
          if n > high[0]:
            f += n - high[0]
          heappush(high, n)
          heappush(low, -heappop(high))
        else:
          f += - n - low[0]
          heappush(low, -n)

    odd = ~odd
    x = -low[0]
    num_a += 1
### BUGGY CODE ###

k=int(input())
if not k&1:
    print(-1)
    exit()
ks=str(k)
carry=0
d1=int(ks[-1])
i=1
while i<=10**8:
    flag=False
    car=int(carry)
    for j in range(0,10):
        if (d1*j+car)%10==7:
            carry=str((car+k*j)//10)
            if len(carry)==carry.count('7'):
                print(i+len(carry))
                exit()
            flag=True
            break
    if not flag:
        print(-1)
        exit()
    i+=1

### FIXED CODE ###

k=int(input())
mod=7
cnt=1
for i in range(k):
    if mod%k==0:
        print(cnt)
        exit()
    mod=(mod*10+7)%k
    cnt+=1
print(-1)
### BUGGY CODE ###

def examB():
    A = S()
    B = S()
    if len(A)>len(B):
        ans = "GREATER"
    elif len(A)<len(B):
        ans = "LESS"
    else:
        i = 0; k = 0; cur = 0
        while i==k:
            if cur==len(A):
                ans = "EQUAL"
                break
            i = int(A[cur])
            k = int(B[cur])
            if i>k:
                ans = "GREATER"
                break
            elif i<k:
                ans = "LESS"
                break
    print(ans)

import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examB()

### FIXED CODE ###

def examB():
    A = S()
    B = S()
    if len(A)>len(B):
        ans = "GREATER"
    elif len(A)<len(B):
        ans = "LESS"
    else:
        i = 0; k = 0; cur = 0; loop = len(A)
        while i==k:
            if cur==loop:
                ans = "EQUAL"
                break
            i = int(A[cur])
            k = int(B[cur])
            if i>k:
                ans = "GREATER"
                break
            elif i<k:
                ans = "LESS"
                break
            cur +=1
    print(ans)

import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examB()
### BUGGY CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
A = list()
B = list()
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)

nice_count = 0
for tenbodai in range(N):
    for michi in range(M):
        if tenbodai in (A[michi], B[michi]):
            another_tenbodai = A[michi] if tenbodai == B[michi] else B[michi]
            if H[another_tenbodai] >= H[tenbodai]:
                break
    else:
        nice_count += 1

print(nice_count)


### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
A = list()
B = list()
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)

kyuryo = [set() for _ in range(N)]
for michi in range(M):
    kyuryo[A[michi]].add(B[michi])
    kyuryo[B[michi]].add(A[michi])

nice_count = 0
for tenbodai in range(N):
    for neighbor in kyuryo[tenbodai]:
        if H[neighbor] >= H[tenbodai]:
            break
    else:
        nice_count += 1

print(nice_count)
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 7)
graph = defaultdict(list)

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

mod = 10 ** 9 + 7


def dfs(K, fro, to):
    if fro == -1:
        colorNum = K-1
    else:
        colorNum = K-2
    if K < len(graph[fro]):
        return 0
    else:
        caseNum = 1
        for e in graph[fro]:
            if e == fro:
                continue
            caseNum *= colorNum
            colorNum -= 1
            caseNum %= mod
        for e in graph[fro]:
            if e == fro:
                continue
            caseNum *= dfs(K, e, fro)
            caseNum %= mod
    return caseNum


ans = K * dfs(K, 0, -1)
print(ans)

### FIXED CODE ###

import sys

stdin = sys.stdin

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

sys.setrecursionlimit(100005)

n, k = na()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)


# res
def dfs(cur, pre, k, g):
    mod = 1000000007
    ret = 1
    nc = 0 if pre == -1 else 1
    for e in g[cur]:
        if e == pre:
            continue
        nc += 1
        ret = ret * (k-nc) % mod
        ret = ret * dfs(e, cur, k, g) % mod
    return ret % mod


print(dfs(0, -1, k, g) * k % 1000000007)