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

def main():
    from collections import defaultdict
    from heapq import heappop, heappush
    N = int(input())
    edge = defaultdict(list)
    length = []
    
    
    for i in range(N):
        length.append([0]*N)
    for i in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        length[a][b] = length[b][a] = c
    Q,K = map(int,input().split())
    K -= 1
    cost = [0]*N
    length[K][K] = 0
    targets = [(0,K)]
    cost = [10**18]*N
    cost[K] = 0
    visited = [False]*N
    while targets:
        c,t = heappop(targets)
        if visited[t]:
            continue
        cost[t] = c
        visited[t] = True
        for v in edge[t]:
            if cost[v] > cost[t] + length[t][v]:
                heappush(targets,(cost[t] + length[t][v],v))

    out = []
    for i in range(Q):
        x,y = map(lambda x: int(x)-1, input().split())
        out.append(cost[x]+cost[y])

    print('\n'.join(map(str,out)))







main()

### FIXED CODE ###

def main():
    from collections import defaultdict
    from heapq import heappop, heappush
    N = int(input())
    edge = defaultdict(list)
    length = defaultdict(lambda : defaultdict(lambda : 10**20))
    
    for i in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        if b<a:
            a,b = b,a
        length[a][b] = c
    Q,K = map(int,input().split())
    K -= 1
    cost = [0]*N
    length[K][K] = 0
    targets = [(0,K)]
    cost = [10**18]*N
    cost[K] = 0
    visited = [False]*N
    while targets:
        c,t = heappop(targets)
        if visited[t]:
            continue
        cost[t] = c
        visited[t] = True
        for v in edge[t]:
            if cost[v] > cost[t] + length[min(t,v)][max(t,v)]:
                heappush(targets,(cost[t] + length[min(t,v)][max(t,v)],v))

    out = []
    for i in range(Q):
        x,y = map(lambda x: int(x)-1, input().split())
        out.append(cost[x]+cost[y])

    print('\n'.join(map(str,out)))







main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
seen = []
same = set()
ans = 0
pre = -1
flg = False
for i in a:
    if i==pre:
        if flg:
            same.add(i)
        continue
    pre = i
    flg = True
    for j in seen:
        if j*2>i:
            break
        if i%j==0:
            flg = False
            break
    if flg:
        ans += 1
        seen.append(i)
print(ans-len(same))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
if a[0]==1:
    if n==1 or a[1]>1:
        print(1)
    else:
        print(0)
    exit(0)
ok = [True]*(10**6+1)
ans = 0
pre = -1
for i in a:
    if not ok[i]:
        continue
    if i==pre:
        ok[i] = False
        continue
    pre = i
    for j in range(i*2, 10**6+1, i):
        ok[j] = False
for i in a:
    if ok[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [[a[i], i] for i in range(n)]
b.sort(reverse = True)
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(n - i + 1):
        k = i + j - 1
        if k == -1:
            continue
        if i == 0:
            dp[i][j] = dp[i][j - 1] + abs(b[k][1] - (n - j)) * b[k][0]
        elif j == 0:
            dp[i][j] = dp[i - 1][j] + abs(b[k][1] - (i - 1)) * b[k][0]
        else:
            dp[i][j] = max(dp[i][j - 1] + abs(b[k][1] - (n - j)) * b[k][0], dp[i - 1][j] + abs(b[k][1] - (i - 1)) * b[k][0])
ans = 0
for i in range(n + 1):
    ans = max(ans, dp[i][n - i])
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [[a[i], i] for i in range(n)]
b.sort(reverse = True)
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(n - i + 1):
        k = i + j - 1
        if k == -1:
            continue
        if i == 0:
            dp[i][j] = dp[i][j - 1] + abs(b[k][1] - (n - j)) * b[k][0]
        elif j == 0:
            dp[i][j] = dp[i - 1][j] + abs(b[k][1] - (i - 1)) * b[k][0]
        else:
            dp[i][j] = max(dp[i][j - 1] + abs(b[k][1] - (n - j)) * b[k][0], dp[i - 1][j] + abs(b[k][1] - (i - 1)) * b[k][0])
ans = 0
for i in range(n + 1):
    ans = max(ans, dp[i][n - i])
print(ans)
### BUGGY CODE ###

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

def schedule(reward, day, jobs):
    if day > M or not jobs:
        return reward
    else:
        results = []
        for job in jobs:
            if day + job[0] - 1 > M:
                jobs.remove(job)

        if not jobs:
            return reward

        best_jobs = {}
        for job in jobs:
            if job[0] in best_jobs:
                if best_jobs[job[0]][1] < job[1]:
                    best_jobs[job[0]] = job
            else:
                best_jobs[job[0]] = job

        for job in best_jobs.values():
            copied_jobs = list(jobs)
            copied_jobs.remove(job)
            result = schedule(reward + job[1], day + 1, copied_jobs)
            results.append(result)
        return max(results)

print(schedule(0, 1, jobs))


### FIXED CODE ###

import heapq
from collections import defaultdict

N, M = map(int, input().split())
jobs = defaultdict(list)
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs[day].append(value)

ans = 0
hq = []
for day in range(1, M+1):
    for value in jobs[day]:
        heapq.heappush(hq, - value)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

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

I=lambda:list(map(int,input().split()))
n,Ma,Mb=I()
m=[[0,0,0]]+[I()for _ in range(n)]
dp=[[[10**18]*(10*n+1)for _ in range(10*n+1)]for _ in range(n+1)]
dp[0][0][0]=0
for i in range(1,n+1):
    for j in range(10*n+1):
        if j-m[i][0]<0:
            dp[i][j]=dp[i-1][j]
            continue
        for k in range(10*n+1):
            if k-m[i][1]<0:
                dp[i][j][k]=dp[i-1][j][k]
            else:
                dp[i][j][k]=min(dp[i-1][j-m[i][0]][k-m[i][1]]+m[i][2],dp[i-1][j][k])
ans=10**18
for i in range(1,10*n+1):
    j=Mb*i/Ma
    if j==int(j) and j<10*n+2:
        ans=min(ans,dp[-1][i][int(j)])
print(-(ans==10**18)or ans)

### FIXED CODE ###

I=lambda:list(map(int,input().split()))
n,Ma,Mb=I()
m=[[0,0,0]]+[I()for _ in range(n)]
dp=[[[10**18]*(10*n+1)for _ in range(10*n+1)]for _ in range(n+1)]
dp[0][0][0]=0
for i in range(1,n+1):
    for j in range(10*n+1):
        if j-m[i][0]<0:
            dp[i][j]=dp[i-1][j]
            continue
        for k in range(10*n+1):
            if k-m[i][1]<0:
                dp[i][j][k]=dp[i-1][j][k]
            else:
                dp[i][j][k]=min(dp[i-1][j-m[i][0]][k-m[i][1]]+m[i][2],dp[i-1][j][k])
ans=10**18
for i in range(1,10*n+1):
    j=Mb*i/Ma
    if j==int(j) and j<10*n+2:
        ans=min(ans,dp[-1][i][int(j)])
print(-(ans==10**18)or ans)
### BUGGY CODE ###

import bisect

N = int(input())

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

ans = 0
mem_idx_a = {}
for idx_c in range(N):
  idx_b = bisect.bisect_left(B,C[idx_c])
  if idx_b == 0: continue
  for i in range(idx_b):
    if B[i] in mem_idx_a:
      idx_a = mem_idx_a[B[i]]
    else:
      idx_a = bisect.bisect_left(A,B[i])
      mem_idx_a[B[i]] = idx_a
    ans += idx_a
print(ans)

### FIXED CODE ###

import bisect

N = int(input())

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

ans = 0
mem_idx_a = {}
for idx_b in range(N):
  idx_c = bisect.bisect_right(C,B[idx_b])
  idx_a = bisect.bisect_left(A,B[idx_b])
  ans += (N-idx_c)*idx_a
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=list(input())
A=[[]*(N//K+1) for i in range(K)]
for i in range(N):
    for j in range(K):
        if i%K==j:
            A[j].append(T[i])
        else:
            pass
ans=0
flag=None
for i in range(K):
    for j in range(len(A[i])):
        if j==0:
            if A[i][j]=='r':
                ans+=P
                flag='r'
            elif A[i][j]=='s':
                ans+=R
                flag='s'
            else:
                ans+=S
                flag='p'
        elif A[i][j]==flag:
            flag=None
    
        else:
            if A[i][j]=='r':
                ans+=P
                flag='r'
            elif A[i][j]=='s':
                ans+=R
                flag='s'
            else:
                ans+=S
                flag='p'
print(ans)
        

### FIXED CODE ###

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

ans=0

for j in range(len(T)):
    if j<K:
        if T[j]=='r':
            ans+=P
        elif T[j]=='s':
            ans+=R
        else:
            ans+=S
    elif j>=K and T[j]!=T[j-K]:
        if T[j]=='r':
            ans+=P
        elif T[j]=='s':
            ans+=R
        else:
            ans+=S
    else:
        T[j]=''
print(ans)
### BUGGY CODE ###

n=int(input())
cnt=0
A,B=[],[]
for i in range(n):
  a,b=list(map(int,input().split()))
  A.append(a)
  B.append(b)

for i in range(n)[::-1]:
  add=(B[i]*(A[i]//B[i]+1)-A[i]) if A[i]%B[i]!=0 else 0
  A[:i+1]=map(lambda x:x+add,A[:i+1])
  cnt+=add
print(cnt)


### FIXED CODE ###

n=int(input())
cnt=0
A,B=[],[]
for i in range(n):
  a,b=list(map(int,input().split()))
  A.append(a)
  B.append(b)

for i in range(n)[::-1]:
  if (A[i]+cnt)%B[i]==0:
    continue
  else:
    cnt+=(B[i]*((A[i]+cnt)//B[i]+1)-(A[i]+cnt))
print(cnt)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    # from bisect import bisect_left
    ans = 0
    for i in range(2, N):
        # i番目を最長辺とする
        for j in range(i):
            for k in range(j+1, i):
                if L[j]+L[k] > L[i]:
                    ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    L_pair = []
    for i in range(N):
        for j in range(i+1, N):
            L_pair.append((i, j))

    def is_ok(mid, i, j):
        if L[mid] < L[i] + L[j]:
            return True
        else:
            return False

    def binary_search_meguru(i, j):
        left = j
        right = N
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(mid, i, j):
                left = mid
            else:
                right = mid
        return right

    ans = 0
    for i, j in L_pair:
        r = binary_search_meguru(i, j)
        ans += r - (j + 1)
    print(ans)


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

import sys

periphery, n = map(int, input().split())
xxx = list(map(int, sys.stdin.readlines()))
xxx.append(xxx[0] + periphery)
xxx.append(periphery - xxx[-2])
dp = [[0, 0] for _ in range(n + 1)]
for w in range(1, n):
    ndp = [[0, 0] for _ in range(n + 1)]
    for l in range(n - w):
        r = l + w
        pos_l, pos_l1, pos_r1, pos_r = xxx[l], xxx[l + 1], xxx[r - 1], xxx[r]
        pos_left_plant_left = dp[l + 1][0] + (pos_l1 - pos_l)
        pos_left_plant_right = dp[l][0] + (periphery - (pos_r - pos_l))
        pos_right_plant_left = dp[l + 1][1] + (periphery - (pos_r - pos_l))
        pos_right_plant_right = dp[l][1] + (pos_r - pos_r1)
        ndp[l][0] = max(pos_left_plant_left, pos_right_plant_left)
        ndp[l][1] = max(pos_left_plant_right, pos_right_plant_right)
    dp = ndp
print(max(dp[0][0] + xxx[0], dp[0][1] + xxx[-1]))


### FIXED CODE ###

import sys
from itertools import accumulate

circumference, n = map(int, input().split())
lll = list(map(int, sys.stdin.readlines()))
rrr = [circumference - l for l in lll]
rrr.reverse()
lll = [0] + lll
rrr = [0] + rrr
acc_l = list(accumulate(lll))
acc_r = list(accumulate(rrr))

ans = max(lll[-1], rrr[-1])
for take_l in range(1, n):
    take_r = n - take_l

    # l last
    tmp_l = lll[take_l] + 2 * (acc_l[take_l - 1] + acc_r[take_r])
    # r last
    tmp_r = rrr[take_r] + 2 * (acc_r[take_r - 1] + acc_l[take_l])

    if take_l < take_r:
        tmp_l -= 2 * acc_r[take_r - take_l]
        tmp_r -= 2 * acc_r[take_r - 1 - take_l]
    elif take_l > take_r:
        tmp_l -= 2 * acc_l[take_l - 1 - take_r]
        tmp_r -= 2 * acc_l[take_l - take_r]

    ans = max(ans, tmp_l, tmp_r)
print(ans)
### BUGGY CODE ###

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


def max_search(s, t):
    for i in range(s):
        if (s-i) % t == 0:
            return (s-i) // t
    return 0

a_max = max_search(a-1, x)
b_max = max_search(b, x)
if a == 0:
    b_max += 1
print(b_max-a_max)

### FIXED CODE ###

a, b, x = map(int, input().split())
a_max = max(((a-1) // x, 0))
b_max = b // x
if a == 0:
    b_max += 1
print(b_max-a_max)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = [a[0]]
pre = 0
for i in range(1, n):
    if pre == 0:
        q.append(a[i])
        pre ^=1
    else:
        q.insert(0, a[i])
        pre ^= 1

if n % 2 == 0:
    print(" ".join(map(str, q[::-1])))
else:
    print(" ".join(map(str, q)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
p = [a[i] for i in range(0, n, 2)]
q = [a[i] for i in range(1, n, 2)]

if n % 2 == 0:
    print(" ".join(map(str, q[::-1] + p)))
else:
    print(" ".join(map(str, p[::-1] + q)))
### BUGGY CODE ###

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

# process
R = []
G = []
B = []
for i, s in enumerate(list(S)):
    if s == 'R':
        R.append(i)
    elif s == 'G':
        G.append(i)
    else:
        B.append(i)

ans = 0
for r in R:
    for g in G:
        for b in B:
            if r < g:
                if g < b:
                    if b-g != g-r:
                        ans += 1
                else:
                    if r < b:
                        if g-b != b-r:
                            ans += 1
                    else:
                        if g-r != r-b:
                            ans += 1
            else:
                if r < b:
                    if b-r != r-g:
                        ans += 1
                else:
                    if g < b:
                        if r-b != b-g:
                            ans += 1
                    else:
                        if r-g != g-b:
                            ans += 1

# output
print(ans)


### FIXED CODE ###

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

# process
ans = S.count('R')*S.count('G')*S.count('B')
for i in range(N):
    for j in range(N):
        if i-j<0 or i+j >= N:
            break
        x = S[i-j]
        y = S[i]
        z = S[i+j]

        if x!= y and x != z and y != z:
            ans -= 1
            
# output
print(ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
s=input()
A=[]
for i in range(N-1):
  if s[i]+s[i+1]=="AC":
    A.append(1)
  else:
    A.append(0)
for i in range(Q):
  l,r=map(int,input().split())
  print(sum(A[l-1:r-1]))

### FIXED CODE ###

N,Q=map(int,input().split())
s=input()
A=[0]
for i in range(N-1):
  if s[i]+s[i+1]=="AC":
    A.append(A[i]+1)
  else:
    A.append(A[i])
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])
### BUGGY CODE ###

def combination(n, r):
    r = min(n - r, r)
    result = 1
    for i in range(n, n - r, -1):
        result *= i
    for i in range(1, r + 1):
        result //= i
    return result


N, M, K = map(int, input().split())
mod = 10 ** 9 + 7

NM = N * M
fa = [1] * (NM + 1)

for i in range(1, NM + 1):
    fa[i] = fa[i - 1] * i
    fa[i] %= mod

ans = 0
for i in range(1, N):
    ans += i * M * M * (N - i)
    ans %= mod

for i in range(1, M):
    ans += i * N * N *(M-i)
    ans %= mod

ans *= combination(NM-2, K-2)
ans %= mod
print(ans)


### FIXED CODE ###

class FactMod:

    def __init__(self, n, mod):
        self.mod = mod
        self.f = [1] * (n + 1)
        for i in range(1, n + 1):
            self.f[i] = self.f[i - 1] * i % mod

        self.inv = [pow(self.f[-1], mod - 2, mod)]
        for i in reversed(range(1, n + 1)):
            self.inv.append(self.inv[-1] * i % mod)
        self.inv.reverse()

    def fact(self, n):
        """
        :return: n!
        """
        return self.f[n]

    def comb(self, n, r):
        """
        :return: nCr
        """
        return self.f[n] * self.inv[n - r] * self.inv[r] % self.mod

N, M, K = map(int, input().split())
mod = 10 ** 9 + 7

NM = N * M
fa = [1] * (NM + 1)

for i in range(1, NM + 1):
    fa[i] = (fa[i - 1] * i) % mod

ans = 0
for i in range(1, N):
    ans += (i * M * M * (N - i)) % mod
    ans %= mod

for i in range(1, M):
    ans += (i * N * N *(M-i)) % mod
    ans %= mod

factmod = FactMod(NM-2, mod)
ans *= factmod.comb(NM-2, K-2)
ans %= mod
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Jun 24 20:53:22 2020

@author: NEC-PCuser
"""
def calc_pow(K, mod):
    pow25 = 1
    pow26 = 1
    li_pow25 = [1]
    li_pow26 = [1]
    for i in range(K + 1):
        pow25 *= 25
        pow25 %= mod
        li_pow25.append(pow25)
        pow26 *= 26
        pow26 %= mod
        li_pow26.append(pow26)
    return li_pow25, li_pow26
    
if __name__ == '__main__':
    K = int(input())
    n = len(input())
    mod = 10**9+7 #出力の制限
    #25 25 a 25 25 25 b 25 25  c  26 26
    cmb = 1
    ans = 0
    pow25, pow26 = calc_pow(K, mod)
    li = []
    for i in range(0, K + 1):
        ans1 = (pow(25, i, mod) * cmb) % mod
        ans2 = pow(26, K - i, mod)
        cmb = (cmb * (n + i) // (i + 1))
        ans = (ans + (ans1 * ans2) % mod) % mod
        #li.append(pow(25, i, mod))
    
    print(ans)
        

### FIXED CODE ###

n = int(input())
s = input()
 
S = len(s)
mod = 10 ** 9 + 7
 
tmp_ans = pow(26, n, mod)
div = pow(26, -1, mod)
 
ans = tmp_ans
 
for i in range(1, n+1):
    tmp_ans = (tmp_ans * 25 * div) % mod
    tmp_ans = ((tmp_ans * (S-1+i)) * pow(i, -1, mod)) % mod
    ans = (ans + tmp_ans) % mod
 
ans %= mod
 
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
T, D = {i: [] for i in range(N)}, [-1] * N
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    T[a - 1].append((b - 1, c))
    T[b - 1].append((a - 1, c))


def dfs(p, c, d):
    D[c] = d
    for c2, d2 in T[c]:
        if c2 != p:
            dfs(c, c2, d + d2)


Q, K = map(int, input().split())
dfs(-1, K - 1, 0)
for _ in range(Q):
    x, y = map(int, input().split())
    print(D[x - 1] + D[y - 1])


### FIXED CODE ###

N = int(input())
neig = [[] for _ in range(N)]

for _ in range(N - 1):
    a, b, c = map(int, input().split())
    neig[a - 1].append((b - 1, c))
    neig[b - 1].append((a - 1, c))

Q, K = map(int, input().split())

S, D = [(K - 1, K - 1)], [0] * N
while len(S) > 0:
    p, pp = S.pop()
    for c, d in neig[p]:
        if not c == pp:
            D[c] = D[p] + d
            S.append((c, p))

for _ in range(Q):
    x, y = map(int, input().split())
    print(D[x - 1] + D[y - 1])
### BUGGY CODE ###

from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = deque()
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

while que:
  p = que.popleft()
  #if (p[0] == x2) & (p[1] == y2):
  #  break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      cnt = 1
      while (dp[nx][ny] == 0) | (
            (dp[nx][ny] >= (dp[p[0]][p[1]] + 1)) & (dp[nx][ny] > 0)):
        que.append((nx,ny))
        dp[nx][ny] = dp[p[0]][p[1]] + 1
        cnt += 1
        nnx = nx + dx[i]
        nny = ny + dy[i]
        if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt > k):
          break
        nx = nnx
        ny = nny

if dp[x2][y2] != 0:
  print(dp[x2][y2]-1)
else:
  print(-1)

### FIXED CODE ###

#import heapq
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
dp = [[-1]*w for _ in range(h)]
#que = []
que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
#heapq.heappush(que, (dp[x1][y1], [x1,y1]))
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  x,y=que.popleft()
  if x==x2 and y==y2:
    exit(print(dp[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or c[xx][yy]=="@":break
      if 0<=dp[xx][yy]<=dp[x][y]:break
      if dp[xx][yy]==-1:que.append((xx,yy))
      dp[xx][yy]=dp[x][y]+1
print(-1)
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(n):
    ans *= i+1
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
ans = 1
c = 10**9+7
for i in range(n):
    ans = (ans*(i+1))%c
print(ans)
### BUGGY CODE ###

# ABC 165 D - Floor Function

a,b,n = map(int, input().split())
l =[(int((a/b)*(i+1)) - a*int((i+1)/b)) - (int((a/b)*(i)) - a*int((i)/b)) for i in range(1, n+1)]

left = 0
right = n-1
mid = (left+right)//2

while right - left > 1:
    if l[mid] <= 0:
        right = mid
        mid = (left+right)//2
    else:
        left = mid
        mid = (left+right)//2

res = right +1
print((int((a/b)*(res)) - a*int((res)/b)))

### FIXED CODE ###

# ABC 165 D - Floor Function

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

def func(i):
    return int(i*a/b) - a*int(i/b)

print(func(min(b-1, n)))
### BUGGY CODE ###

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

### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
c = collections.Counter(A)
for i in range(1,N+1):
    print(c[i])
### BUGGY CODE ###

N,M=map(int,input().split())
all_pairs = N * (N - 1) // 2
island = [set([i]) for i in range(1,N+1)]
A=[0 for i in range(M)]
B=[0 for i in range(M)]
ans=[0 for i in range(M)]
for i in range(M):
    A[i],B[i]=map(int,input().split())

for i in range(M-1, -1, -1):
    a,b=A[i],B[i]
    a2 = next(filter(lambda e:a in e, island), None)
    b2 = next(filter(lambda e:b in e, island), None)
    if a2 != b2:
        a2 |= b2
        b2.clear()
    #print(island)
    ans[i] = all_pairs
    for j in range(N):
        l = len(island[j])
        if l != 0:
            ans[i] -= l * (l - 1) // 2

for i in range(1,M):
    print(ans[i])
print(all_pairs)


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        # 最初はすべての根が自分自身である
        self.parent = [-1 for i in range(n)]

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

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

    def connect(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.size(x) < self.size(y):
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x

N, M = map(int,input().split())
AB = []
ans = [0 for i in range(M+1)]
for i in range(M):
    AB.append(list(map(int,input().split())))

uni = UnionFind(N)
ans[M] = N * (N - 1) // 2
for i in range(M-1, 0, -1):
    a,b = AB[i]
    a-=1
    b-=1
    if uni.root(a) == uni.root(b):
        ans[i] = ans[i+1]
    else:
        ans[i] = ans[i+1] - uni.size(a) * uni.size(b)
        uni.connect(a,b)

for i in range(1,M+1):
    print(ans[i])
### BUGGY CODE ###

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

num = 0
sortedA = []

end = len(a) - 1

for i in range(0, end):
    if i == 0:
        sortedA.append(''.join(sorted(a[0])))
    for j in range(i + 1, end + 1):
        if i == 0:
            sortedA.append(''.join(sorted(a[j])))
        if sortedA[i] == sortedA[j]:
            num = num + 1
print(num)

### FIXED CODE ###

import sys
import collections

n=int(input())
a=[''.join(sorted(input())) for _ in range(n)]

ans = 0
for v in collections.Counter(a).values():
    if v != 1:
        ans += v * (v - 1) // 2
print(ans)