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

from collections import defaultdict
h, w, m = map(int, input().split())
targets = defaultdict(int)
targets_count_yoko = [0]*w
targets_count_tate = [0]*h
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    targets_count_yoko[x] += 1
    targets_count_tate[y] += 1
    targets[(y, x)] = -1

max_row = max(targets_count_yoko)
max_line = max(targets_count_tate)
y_idx = []
x_idx = []
for i in range(w):
    if targets_count_yoko[i] == max_row:
        x_idx.append(i)
for i in range(h):
    if targets_count_tate[i] == max_line:
        y_idx.append(i)


ans = 0
for y in y_idx:
    for x in x_idx:
        res = max_line + max_row + targets[(y, x)]
        ans = max(ans, res)

print(ans)


### FIXED CODE ###

from collections import defaultdict
h, w, m = map(int, input().split())
targets = defaultdict(int)
targets_count_yoko = defaultdict(int)
targets_count_tate = defaultdict(int)
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    targets_count_yoko[x] += 1
    targets_count_tate[y] += 1
    targets[(y, x)] = -1

max_row = max(targets_count_yoko.values())
max_line = max(targets_count_tate.values())
y_idx = defaultdict(bool)
x_idx = defaultdict(bool)
max_count_x = 0
max_count_y = 0
for i in range(w):
    if targets_count_yoko[i] == max_row:
        x_idx[i] = True
        max_count_x += 1
for i in range(h):
    if targets_count_tate[i] == max_line:
        y_idx[i] = True
        max_count_y += 1


ans = max_line + max_row
kumi = max_count_x*max_count_y
for key_y, key_x in targets.keys():
    if y_idx[key_y] and x_idx[key_x]:
        kumi -= 1
    if kumi == 0:
        break

if kumi == 0:
    print(ans-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
import math
def isPrime(n):
    if n == 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        if isPrime(p):
            print("1")
            sys.exit()
        ans = 1
        cnt = 0
        while p % 2 == 0:
            p //= 2
            cnt += 1
        if cnt >= n:
            ans *= 2**(cnt//n)
        x = 3
        while x**n <= p:
            cnt = 0
            while p % x == 0:
                p //= x
                cnt += 1
            if cnt >= n:
                ans *= x**(cnt//n)
            x += 2
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from math import log
def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        if n > int(log(p, 2))+2:
            print("1")
            sys.exit()
        if p % (2**n) == 0:
            while p % (2**n) == 0:
                ans *= 2
                p //= (2**n)
        for i in range(3, 10**6+1, 2):
            while p % (i**n) == 0:
                ans *= i
                p //= (i**n)
        print(ans)

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

N=int(input())
A=list(map(int,input().split()))
B=[0]*N
for i in range (0,N):
    B[i]=A.index(i+1)+1

    
print(*B)


### FIXED CODE ###

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

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
c = [A.count(i + 1) for i in range(N)]
ans = [c[i] * (c[i] - 1) // 2 for i in range(N)]

for val in A:
  m = c[val - 1] - 1
  print(sum(ans) - m)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
c = [0 for i in range(N)]

for i in range(N):
  c[A[i] - 1] += 1

ans = [c[i] * (c[i] - 1) // 2 for i in range(N)]
s = sum(ans)

for val in A:
  m = c[val - 1] - 1
  print(s - m)
### BUGGY CODE ###

n,m=map(int,input().split())
cost=[]
count=[]
ans=0
temp=0
for i in range(n):
    a,b=map(int,input().split())
    cost.append(a)
    count.append(b)
for i in range(len(cost)):
    ans+=min(cost)*count[cost.index(min(cost))]
    temp+=count[cost.index(min(cost))]
#   print("ans,temp,min(cost),min(count)=",ans,temp,min(cost),count[cost.index(min(cost))])
    if temp>=m:
        ans-=min(cost)*(temp-m)
        break
    else:
        count.remove(count[cost.index(min(cost))])
        cost.remove(min(cost))
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
list=[list(map(int,input().split())) for _ in range(n)]
list.sort()
ans=0
temp=0
for i in range(n):
    ans+=list[i][0]*list[i][1]
    temp+=list[i][1]
    if temp>=m:
        ans-=list[i][0]*(temp-m)
        print(ans)
        break
### BUGGY CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
i = 1
result = 0
result2=[]
for b in range(abs(max(a))*-1,abs(max(a))):
  for data in a:
    result = result + abs(data - b -i)
    i += 1
  result2.append(result)
  result = 0
  i = 0

print(min(result2))

### FIXED CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
B = [ av - i  for i, av in enumerate(a,1)]
B.sort()

middle = n //2
b = B[middle]

result = 0
for a2 in B:
  result = result + abs(a2 -b)
print(result)
### BUGGY CODE ###

import sys
import collections
sys.setrecursionlimit(100000)
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n, m = nm()
memo = [-1 for i in range(max(n, m) + 1)]
mod = 10 ** 9 + 7

for i in range(1, max(n, m) + 1):
    if memo[i] != -1:
        continue
    elif i == 1:
        memo[i] = 1
    else:
        memo[i] = i * memo[i - 1]

if abs(n - m) >= 2:
    print(0)
else:
    nn = memo[n] % mod
    mm = memo[m] % mod
    if n == m:
        print(2 * nn * mm % mod)
    else:
        print(nn * mm % mod)


### FIXED CODE ###

import sys
import collections
sys.setrecursionlimit(100000)
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n, m = nm()
memo = [1 for _ in range(max(n, m) + 1)]
mod = 10 ** 9 + 7

for i in range(1, max(n, m) + 1):
    memo[i] = memo[i - 1] * i % mod

if abs(n - m) >= 2:
    print(0)
else:
    nn = memo[n] % mod
    mm = memo[m] % mod
    if n == m:
        print(2 * nn * mm % mod)
    else:
        print(nn * mm % mod)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = 0
for i in P:
    cnt = 0
    r = 0
    for j in P:
        r += 1
        if i > j:
            continue
        cnt += 1
        if i == j:
            break
    if cnt == r:
        ans += 1
print(ans)

### FIXED CODE ###

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

cnt = 0
mi = P[0]
for i in range(N):
	if P[i] <= mi:
		mi = P[i]
		cnt += 1
print(cnt)
### BUGGY CODE ###

a, b, x = map(int, input().split())
count = 0
for i in range(a, b+1):
    if i % x == 0:
        count += 1

print(count)



### FIXED CODE ###

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

count = b//x - (a-1)//x if a > 0 else b//x + 1

print(count)
### BUGGY CODE ###

import heapq
import copy

N=int(input())
A=[-int(input()) for i in range(N)]
#print(N,A)

for j in range(N):
    copy_A=copy.copy(A)
    item=copy_A.pop(j)  #負
    #print(item)
    heapq.heapify(copy_A)
    #print(copy_A)
    MAX=-copy_A[0]  #正
    print(MAX)





### FIXED CODE ###

import copy

N=int(input())
A=[]
for _ in range(N):
    A.append(int(input()))

A_max=max(A)
ind_max=A.index(A_max)
B=copy.copy(A)
B.remove(A_max)
B_max=max(B)

for i in range(N):
    if A[i]!=A_max:
        print(A_max)
    else:
        print(B_max)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

ac_idx = []
for i in range(N-1):
    if S[i:i+2] == 'AC':
        ac_idx.append(i)


for _ in range(Q):
    l, r = map(int, input().split())
    cnt = 0
    for idx in ac_idx:
        if idx >= l-1 and idx+1 <= r-1:
            cnt += 1
    print(cnt)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

ac_cnt = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        ac_cnt[i] = ac_cnt[i-1] + 1
    else:
        ac_cnt[i] = ac_cnt[i-1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = ac_cnt[r-1] - ac_cnt[l-1]
    print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
s = s[::-1]

memo = [0] * 2019
memo[0] += 1

num = 0
ten = 1
for i in s:
    num += int(i) * ten
    memo[num%2019] += 1
    ten *= 10

ans = 0
for p in memo:
    ans += p*(p-1)//2

print(ans)

### FIXED CODE ###

s = input()
n = len(s)

memo = [0] * 2019
memo[0] += 1

num = 0
t = 1
for i in reversed(s):
    num += int(i) * t
    num %= 2019
    t *= 10
    t %= 2019
    memo[num] += 1

ans = 0
for p in memo:
    ans += p*(p-1)//2

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

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


ans = 0
for i in range(1, n+1):
  t = (a*i//b) - a*(i//b)
  ans = max(ans,t)
print(ans)

### FIXED CODE ###

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

x = min(b-1, n)
print(a*x//b -a*(x//b))
### BUGGY CODE ###

i = list(map(int, input().split()))
l = [list(input()) for j in range(i[0])]
row_n = i[0]
column_n = i[1]
coulmn = 1
row = 0
n_blacks = []
for i_r, j in enumerate(l):
    for i_c, k in enumerate(j):
        if k == "#":
            n_blacks.append([i_r,i_c])

cn = 0
while "." in [flatten for inner in l for flatten in inner]:
    blacks = []
    for i in range(len(n_blacks)):
        black = n_blacks[i]
        if black[row]-1 >= 0:
            l[black[row]-1][black[coulmn]] = "#"
            blacks.append([black[row]-1, black[coulmn]])
        if black[row]+1 < row_n:
            l[black[row]+1][black[coulmn]] = "#"
            blacks.append([black[row]+1, black[coulmn]])
        if black[coulmn]-1 >= 0:
            l[black[row]][black[coulmn]-1] = "#"
            blacks.append([black[row], black[coulmn]-1])
        if black[coulmn]+1 < column_n:
            l[black[row]][black[coulmn]+1] = "#"
            blacks.append([black[row], black[coulmn]+1])
        next_blacks = blacks
    n_blacks = blacks
    cn += 1

print(cn)

### FIXED CODE ###

from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

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

from collections import Counter
h,w=map(int,input().split())
#a=[list(input()) for i in range(w)]
a=[]
flag=True
for i in range(h):
  a+=list(input())
ca=Counter(a)
if h%2==0 and w%2==0:
  for i in ca:
    if ca[i]%4!=0:
      flag=False
      print('No')
      break
  if flag:
    print('Yes')

elif h%2!=0 and w%2!=0:
  yon=(h-1)*(w-1)
  ni=h*w-yon-1
  iti=1
  for i in ca:
    while ca[i]>0:
      if ca[i]%4==0 and yon>0:
        ca[i]-=4
        yon-=4
      elif ca[i]%2==0 and ni>0:
        ni-=2
        ca[i]-=2
      elif iti>0:
        iti-=1
        ca[i]-=1
  if yon==0 and ni==0 and iti==0:
    print('Yes')
  else:
    print('No')
else:
  if h%2==0:
    yon=(h)*(w-1)
  else:
    yon=(h-1)*(w)
  ni=h*w-yon
  for i in ca:
    while ca[i]>0:
      if ca[i]%4==0 and yon>0:
        ca[i]-=4
        yon-=4
      elif ca[i]%2==0 and ni>0:
        ni-=2
        ca[i]-=2
      else:
        break
  if yon==0 and ni==0:
    print('Yes')
  else:
    print('No')
  
  

### FIXED CODE ###

from collections import Counter
h,w=map(int,input().split())
#a=[list(input()) for i in range(w)]
a=[]
flag=True
for i in range(h):
  a+=list(input())
ca=Counter(a)
if h%2==0 and w%2==0:
  for i in ca:
    if ca[i]%4!=0:
      flag=False
      print('No')
      break
  if flag:
    print('Yes')

elif h%2!=0 and w%2!=0:
  yon=(h-1)*(w-1)
  ni=h*w-yon-1
  iti=1
  for i in ca:
    while ca[i]>0:
      if ca[i]%4==0 and yon>0:
        ca[i]-=4
        yon-=4
      elif ca[i]%2==0 and ni>0:
        ni-=2
        ca[i]-=2
      elif iti>0:
        iti-=1
        ca[i]-=1
      else:
        break
  if yon==0 and ni==0 and iti==0:
    print('Yes')
  else:
    print('No')
else:
  if h%2==0:
    yon=(h)*(w-1)
  else:
    yon=(h-1)*(w)
  ni=h*w-yon
  for i in ca:
    while ca[i]>0:
      if ca[i]%4==0 and yon>0:
        ca[i]-=4
        yon-=4
      elif ca[i]%2==0 and ni>0:
        ni-=2
        ca[i]-=2
      else:
        break
  if yon==0 and ni==0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

n = int(input())
list = []
for i in range(n) :
    list.append(int(input()))
for i in range(n) :
    sorted_list = sorted(list, reverse=True)
    idx = sorted_list.index(list[i])
    sorted_list.pop(idx)
    print(sorted_list[0])


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
sorted_list = sorted(a, reverse=True)
a_max = sorted_list[0]
a_sec = sorted_list[1]
for i in range(n) :
    if a[i] != a_max :
        print(a_max)
    else :
        print(a_sec)
### BUGGY CODE ###

def sub():
    INF = 10 ** 12
    N, K = map(int, input().split())
    hs = [int(e) for e in input().split()]
    optimal_values = [INF for _ in range(N)]
    optimal_values[0] = 0
    for i in range(0, N):
        for j in range(1, K + 1):
            p = i + j
            if p < N:
                optimal_values[p] = min(
                    optimal_values[p], optimal_values[i] + abs(hs[p] - hs[i])
                )
            else:
                break
    print(optimal_values[-1])
    # print(optimal_values)


sub()


### FIXED CODE ###

def sub():
    INF = 10 ** 12
    N, K = map(int, input().split())
    hs = [int(e) for e in input().split()]
    optimal_values = [INF for _ in range(N)]
    optimal_values[0] = 0
    for i in range(0, N):
        for j in range(1, K + 1):
            p = i + j
            if p < N:
                optimal_values[p] = min(
                    optimal_values[p], optimal_values[i] + abs(hs[p] - hs[i])
                )
            else:
                break
    print(optimal_values[-1])
    # print(optimal_values)


sub()
### BUGGY CODE ###

N, M = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

List.sort(key=lambda x: x[0])
List_S = []
 
result = 0
p = 0
 
for i in range(1,M+1):
    add = 0
    for j in range(p,N):
        if List[j][0] <= i:
            List_S.append(List[j][1])
            p += 1
            add = 1
        else:
            break
    if len(List_S) != 0:
        if add == 1:
            List_S.sort(reverse = True)
        result += List_S[0]
        del List_S[0]
 
print(result)

### FIXED CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline

N, M = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

List.sort(key=itemgetter(0))
List_S = [0]
 
result = 0
p = 0

for i in range(1, M+1):
    add = 0
    add_list = []
    while p < N and List[p][0] == i:
        if List_S[len(List_S)-1] < List[p][1]:            
            List_S.append(List[p][1])
        else:
            add_list.append(List[p][1])
            add += 1
        p += 1
            
    if len(List_S) != 1:
        result += List_S.pop()
        if add > 0:
            List_S.extend(add_list)
            List_S.sort()
 
print(result)
### BUGGY CODE ###

import numpy as np

def LCS():
  X = input()
  Y = input()
  dp = [["" for i in range(len(X) + 1) ]for i in range(len(Y) + 1)]
  for y in range(len(Y)):
    for x in range(len(X)):
      if Y[y] == X[x]:
        #Xのi文字目とYのj文字目が一致した時のみ値が更新される
        #文字列が一致する直線、i - 1,j - 1目までの最大一致数に、1を足す
        dp[y + 1][x + 1] = dp[y][x] + X[x]
      else:
        a = dp[y][x]
        b = dp[y + 1][x]
        c = dp[y][x + 1]
        m = max(len(b),len(c))
        if len(a) > len(b) or len(a) > len(c):
          continue
        if m == len(c):
          dp[y + 1][x + 1] = c
        elif m == len(b):
          dp[y + 1][x + 1] = b
    
  print(dp[-1][-1])
  
LCS()


### FIXED CODE ###

import numpy as np
#文字列をASCII codeのリストで管理
S = np.array([ord(i) - 97 for i in input()], dtype=int)
T = np.array([ord(i) - 97 for i in input()], dtype=int)
ls = len(S)
lt = len(T)
#S[i] == T[j]であれば、i * j行列の[i,j]成分が1となる行列
equal = np.equal.outer(S,T).astype(int)
#print(equal)
 
dp = [np.zeros(lt + 1,dtype = int)]
#print(dp)
for i in range(ls):
  #追加された最後のdp列をx,newDPとする
  x = dp[-1].copy()
  newDP = x.copy()
  #一致しているところで1を足し、そうでないところはそのまま
  newDP[1:] = np.maximum(x[:-1] + equal[i],newDP[1:])
  #dp[i] = i以前のdpの最大値に更新
  np.maximum.accumulate(newDP, out = newDP)
  #最大共通部分を計算するだけなら一列のdp列を使い回せば良いが
  #文字列の復元のために、dp列を追加する
  dp.append(newDP)
  #print(dp)
 
 
ans = ""
i, j = ls, lt
#数列の復元と文字列への復元
while i > 0 and j > 0:
  if S[i - 1] == T[j - 1]:
    ans += chr(S[i - 1] + 97)
    i -= 1
    j -= 1
    continue
  if dp[i][j] == dp[i - 1][j]:
    i -= 1
  else:
    j -= 1

#リバース
print(ans[::-1])
### BUGGY CODE ###

def resolve():
    from fractions import gcd
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    lsd = a[0]
    for i in range(1, n):
        lsd = (lsd * a[i]) // gcd(lsd, a[i])
 
    ans = 0
    for i in range(n):
        ans += (lsd//a[i]) % mod
 
    print(int(ans % mod))
resolve()

### FIXED CODE ###

def resolve():
    def lcm(X, Y):
        x = X
        y = Y
        if y > x:
            x, y = y, x
        while x % y != 0:
            x, y = y, x % y
        return X * Y // y
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    lsd = a[0]
    for i in range(1, n):
        lsd = lcm(lsd, a[i])
    lsd = lsd % mod

    ans = 0
    for i in range(n):
        ans += (lsd * pow(a[i], mod-2, mod)) % mod

    print(int(ans % mod))

resolve()
### BUGGY CODE ###

N, M = [int(_) for _ in input().split()]
A = [int(input()) for _ in range(M)]

dp = [0 for _ in range(N+1)]
P = 10**9 + 7

dp[0] = 1
for i in range(1, N+1):
    if i in A:
        dp[i] = 0
    elif i == 1:
        dp[i] = dp[i-1] % P
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % P
print(dp[-1])


### FIXED CODE ###

N, M = [int(_) for _ in input().split()]
A = set([int(input()) for _ in range(M)])

dp = [0 for _ in range(N+1)]
P = 10**9 + 7

dp[0] = 1
for i in range(1, N+1):
    if i in A:
        dp[i] = 0
    elif i == 1:
        dp[i] = dp[i-1] % P
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % P
print(dp[-1])
### BUGGY CODE ###

N,W = map(int,input().split())
weight = []
value = []

for _ in range(N):
  w,v = map(int,input().split())
  weight.append(w)
  value.append(v)

DP = [[0]*(W+1) for _ in range(N+1)]  

def knapsack(n,w):
  if w >W:
    return -100000000000000000000
  if n >= len(weight):
    return 0
  if DP[n][w] >0:
      return DP[n][w]
  DP[n][w] = max(knapsack(n+1,w),knapsack(n+1,w+weight[n])+value[n])
  return DP[n][w]
print(knapsack(0,0))

### FIXED CODE ###

def dynamicprogramming():
  N, W = map(int, input().split())
  dp = [-1] * (W + 1)
  dp[0] = 0
  for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W - w, -1, -1):
        dpi = dp[i]
        if dpi != -1:
          if dp[i + w] < dpi + v:
            dp[i + w] = dpi + v
  print(max(dp))

dynamicprogramming()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
for i in range(60):
  o=0
  x=1<<i
  for j in a:
    if j&x:o+=1
  ans+=x*o*(n-o)
  ans%=mod
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
x=1
for i in range(60):
  z=o=0
  for j in range(n):
    if a[j]%2:o+=1
    else:z+=1
    a[j]//=2
  ans+=(x*o*z)%mod
  ans%=mod
  x=(x*2)%mod
print(ans)
### BUGGY CODE ###

m = input()
l = list(map(int, input().split()))
ans = 1
tmp = pow(10, 18)
for i in l:
    ans *= i

if ans <= tmp:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import sys

n = sys.stdin.readline()
l = list(map(int, sys.stdin.readline().split()))
tmp = 1000000000000000000

if 0 in l:
    print(0)
else:
    ans = 1
    for i in l:
        ans *= i
        if 1000000000000000000 < ans:
            break
    if ans <= 1000000000000000000:
        print(ans)
    else:
        print(-1)
### BUGGY CODE ###

# D - Triangles
n = (int)(input())
length = list(map(int, input().split()))

sum = 0

for i in range(n):
    for j in range(n):
        for k in range(n):

            a = length[i]
            b = length[j]
            c = length[k]


            if i >= j or i >= k or j >= k:
                continue

            if a < b + c and b < c + a and c < a + b:
                sum += 1

print(sum)

### FIXED CODE ###

# D - Triangles

import bisect

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

sum = 0

length.sort()

for i in range(n):
    for j in range(n):

            a = length[i]
            b = length[j]

            if i < j:
                k = bisect.bisect_left(length, a + b)
                sum += k - j - 1

print(max(0, sum))
### BUGGY CODE ###

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

array = []

for t in range(10 ** 18):
    if len(array) >= n:
        break
    for p in range(a):
        array.append('blue')
    for q in range(b):
        array.append('red')

f = n // (a+b)
g = n % (a+b)

if g <= a:
    print(f * a + g)
    
else:
    print(f * (a+1))

### FIXED CODE ###

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

f = n // (a+b)
g = n % (a+b)

if g <= a:
    print(a * f + g)
    
else:
    print(a * (f+1))
### BUGGY CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 7)


def LI(): return list(map(int, stdin.readline().split()))


inf = 1000000007


def main():
    N, K = LI()
    graph = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = LI()
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    stack = [0]
    ans = 1
    done = [False for _ in range(N)]
    while len(stack) > 0:
        now = stack.pop(0)
        done[now] = True
        cnt = 0
        for x in graph[now]:
            if not done[x]:
                cnt += 1
                stack.append(x)
        if now == 0:
            for i in range(cnt):
                ans = (K - 1 - i) * ans % inf
        else:
            for i in range(cnt):
                ans = (K - 2 - i) * ans % inf
    print(ans * K % inf)


if __name__ == "__main__":
    main()

### 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()