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

N,A = list(map(int,input().split()))
listA = list(map(int,input().split()))
listA.sort()
listB = []
ans = 0
if N >= len(listA):
    print(0)
    exit()
for i in range(A-1):
    listB.append(listA[i+1]-listA[i])
ans = sum(listB)
for i in range(N-1):
    M = max(listB)
    ans -= M
    listB.remove(M)
print(ans)

### FIXED CODE ###

N,A = list(map(int,input().split()))
listA = list(map(int,input().split()))
listB = []
if N >= len(listA):
    print(0)
    exit()
listA.sort()
max_n = listA[-1] - listA[0]
for i in range(A-1):
    listB.append(listA[i+1]-listA[i])
listB.sort(reverse=True)
max_n -= sum(listB[:N-1])
print(max_n)
### BUGGY CODE ###

def main():
    n = int(input())

    s = list(''.join(sorted(input()[:])) for i in range(n))

    count = 0
    for i in range(0, len(s)):
        for j in range(i + 1, len(s)):
            if s[i] == s[j]:
                count += 1

    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())

    count = 0
    found = {}
    for _ in range(n):
        str = ''.join(sorted(input()))
        if str in found:
            count += found[str]
            found[str] += 1
        else:
            found[str] = 1

    print(count)


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

n = int(input())
l = []
for i in range(n):
    s = input()
    if s not in l:
        l.append(s)

print(len(l))

### FIXED CODE ###

from collections import deque
n = int(input())
l = deque()
for i in range(n):
    s = input()
    l.append(s)
print(len(set(l)))
### BUGGY CODE ###

from collections import deque

S = input()
Q = int(input())
a = deque(S)

for i in range(Q):
  A = input().split()
  if A[0] == "1":
    a.reverse()
  else:
    if A[1] == "1":      
      a.appendleft(A[2])
    else:
      a.append(A[2])
print("".join(a))

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
a = deque(S)

flag = 0

for i in range(Q):
  A = input().split()
  if A[0] == "1":
    if flag == 0:
      flag = 1
    else:
      flag = 0
  else:
    if A[1] == "1" and flag == 0 or A[1] == "2" and flag == 1:      
      a.appendleft(A[2])
    else:
      a.append(A[2])

if flag == 1:
  a.reverse()
print("".join(a))
### BUGGY CODE ###

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

for i in range(q):
  b, c = map(int, input().split())
  a_tmp2 = [c if j == b else j for j in a_tmp]
  ans = sum(a_tmp2)
  a_tmp = a_tmp2
  print(ans)
  

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
arr = [0] * 100005
for val in a:
  arr[val] += 1
sums = sum(a)
q = int(input())
for _ in range(q):
  b, c = map(int,input().split())
  diff = (c-b) * (arr[b])
  sums += diff
  print(sums) 
  arr[c] += arr[b]
  arr[b] = 0
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]
uniqued = []
for x in S:
  if not x in uniqued:
    uniqued.append(x)
print(len(uniqued))

### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]
uniqued = list(set(S))
print(len(uniqued))
### BUGGY CODE ###

h, w, d = list(map(int, input().split()))

a_dict = {}
for i in range(h):
  r = list(map(int, input().split()))
  for j in range(w):
    a_dict[r[j]] = [i+1, j+1]

q = int(input())

test = [list(map(int, input().split())) for i in range(q)]

for t in test:
  power = 0
  for i in range((t[1]-t[0])//d):
    current = a_dict[t[0]+i*d]
    _next = a_dict[t[0]+(i+1)*d]
    power += abs(current[0] - _next[0]) + abs(current[1] - _next[1])
  print(power) 

### FIXED CODE ###

h, w, d = list(map(int, input().split()))

a_dict = {}
for i in range(h):
  r = list(map(int, input().split()))
  for j in range(w):
    a_dict[r[j]] = [i+1, j+1]

q = int(input())

need_power = {}

for i in range(1, h*w+1):
  if i <= d:
    need_power[i] = 0
    continue

  need_power[i] = need_power[i-d] + abs(a_dict[i][0] - a_dict[i-d][0]) + abs(a_dict[i][1] - a_dict[i-d][1])

test = [list(map(int, input().split())) for i in range(q)]

for t in test:                                                                                                             
  print(need_power[t[1]] - need_power[t[0]])
### BUGGY CODE ###

N = int(input())
L = []
for i in range(N):
    L.append(str(input()))

list_val = list(set(L))
list_size = [0]*N
for i,v in enumerate(list_val):
    list_size[i] = L.count(v)

max_size = max(list_size)

ans = []
while max(list_size) == max_size:
    max_idx = list_size.index(max_size)
    ans.append(list_val[max_idx])
    list_size[max_idx] = 0
print("\n".join(sorted(ans)))


### FIXED CODE ###

import collections

N = int(input())

s = [input() for i in range(N)]

c = collections.Counter(s)
max_n = max(c.values())

ans = []
for key, val in c.items():
  if val == max_n:
    ans.append(key)
print("\n".join(sorted(list(set(ans)))))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
cost=0
for i in range(n):
  cost=0
  A=a[:]
  if i==0:
    A[i]=0
  else:
    A[i]=A[i-1]
  cost+=abs(A[0]-0)
  for j in range(n-1):
    cost+=abs(A[j+1]-A[j])
  cost+=abs(0-A[-1])
  print(cost,end="\n")

### FIXED CODE ###

n=int(input())
A=[0]+list(map(int,input().split()))+[0]
cost=sum(abs(A[i+1]-A[i]) for i in range(n+1))
for i in range(1,n+1):
    print(cost-abs(A[i+1]-A[i])-abs(A[i]-A[i-1])+abs(A[i+1]-A[i-1]))
### BUGGY CODE ###

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

cnt = 0
for i in range(n):
    if p_list[i] == min(p_list[:i+1]):
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
minn = p_list[0]
for i in range(n):
    minn = min(p_list[i], minn)
    if p_list[i] == minn:
        cnt += 1
print(cnt)
### BUGGY CODE ###


N = int(input())
A = [[-1 for j in range(N+1)] for i in range(N+1)]
ans = [-1 for i in range(N-1)]
edges = [[] for i in range(N+1)]
 
for i in range(N-1):
  a, b = map(int, input().split())
  if i == 0:
    root = a
  edges[a].append((b, i))
  edges[b].append((a,i))
 
def dfs(u):
  visited = ["white"] * (N + 1)
  stack = [(u, -1, -1)]
  mcolor = -1
 
  while stack:
    u, p, c = stack.pop()
    visited[u] = "black"
 
    next = 1
    for (v, i) in edges[u]:
      if v != p and visited[v] != "black":
        if next == c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        stack.append((v, u, next))
        ans[i] = next
        next += 1
  
  return mcolor
 
print(dfs(root))
 
for a in ans:
  print(a)

### FIXED CODE ###


N = int(input())
edges = [[] for _ in range(N+1)]


for i in range(N-1):
  a, b = map(int, input().split())
  if i == 0:
    root = a
  edges[a].append((b, i))
  edges[b].append((a, i))

ans = [-1 for i in range(N-1)]
def dfs(u):
  flag = ["white"] * (N + 1)
  stack = [(u, -1, -1)]

  while stack:
    u, parent, color = stack.pop()
    flag[u] = "black"

    nextColor = 1
    for (next, index) in edges[u]:
      if next != parent and flag[next] != "black":
        if nextColor == color:
          nextColor += 1
        stack.append((next, u, nextColor))
        ans[index] = nextColor
        nextColor += 1

dfs(root)

print(max(ans))

for a in ans:
  print(a)
### BUGGY CODE ###

# ABC164 D - Multiple of 2019
import numpy as np
import math

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019+1)

for i in range(length):
    a[i] = int(s[i]) * pow(10, i) % 2019
d[0] = a[0]

for i in range(length-1):
    d[i+1] = (d[i] + a[i+1]) % 2019
    ans[d[i+1]] += 1

x = ans[np.where(ans > 1)]

print(int(sum([x[i] * (x[i]-1) for i in range(x.shape[0])]) / 2) + d.shape[0] - np.count_nonzero(d))

### FIXED CODE ###

import numpy as np

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = ans[np.nonzero(ans)]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(ans_c.shape[0])]) / 2) + ans[0])
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = t[0]
        hash_table.append(h)
        p = 1
        for i in range(1, len(t)):
            h = (h * base + t[i]) % hash_md
            hash_table.append(h)
            p = p * base % hash_md
            pw.append(p)

    def hash(s):
        res = 0
        for i, c in enumerate(s[::-1]):
            res = (res + pw[i] * (ord(c) - ord_a)) % hash_md
        return res

    # インデックスがi以上j未満の文字列のハッシュ
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

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

    # 初期化
    base = 29
    hash_md = pow(3, 37)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0]
    pw = [1]
    hash_ini(t)

    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        br = False
        w = (ok + ng) // 2
        for i in range(n - 2 * w + 1):
            ptn = hash_ij(i, i + w)
            for j in range(i + w, n - w + 1):
                if hash_ij(j, j + w) == ptn:
                    ok = w
                    br = True
                    break
            if br: break
        else:
            ng = w
    print(ok)

main()


### FIXED CODE ###

# YouTube
def main():
    n = int(input())
    s = input()
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i, c in enumerate(s):
        for j in range(n):
            if c == s[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
    ans = 0
    for i in range(n):
        for j in range(i+1,n+1):
            tmp=min(dp[i][j],j-i)
            ans=max(tmp,ans)
    print(ans)

main()
### BUGGY CODE ###

from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

    def allset(self):
        d = defaultdict(set)
        for i in range(self.n):
            d[self.find(i)].add(i)
        for i in d.keys():
            d[i] = deque(list(d[i]))
        return d

def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    p = list(map(lambda x: x-1,p))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    d = uf.allset()
    for i in range(N):
        tmp = p[i]
        r = uf.find(tmp)
        if not uf.same(r,i):continue
        else:
            pre = p[i]
            if i in d[r]:
                new = i
                #d[r].remove(i)
            else:
                new = d[r].popleft()
            swap = p.index(new)
            p[i] = new
            p[swap] = pre
    for i in range(N):
        if p[i] != i: continue
        else:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))



def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    p = list(map(lambda x: x-1,p))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    for i in range(N):
        tmp = p[i]
        if not uf.same(tmp,i):continue
        else:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, A, B  = [int(x) for x in input().split(" ")]

lst = []
b = 0
r = 0

while b + r <= N:
  for i in range(0,A):
    lst.append("b")
    b += 1
  for i in range(0,B):
    lst.append("r")
    r += 1
    
print(lst[:N].count("b"))

### FIXED CODE ###

N, A, B  = [int(x) for x in input().split(" ")]

print(int(N/(A+B))*A+int(min(N%(A+B),A)))
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    n=int(input())
    a=[int(input()) for _ in range(n)]

    color=[]
    for num in a:
        idx=bisect_left(color,num)
        if idx==0:
            color=[num]+color
        else:
            color[idx-1]=num
    
    print(len(color))    
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_right
    n=int(input())
    a=[int(input()) for _ in range(n)]

    color=[]
    for i in range(n-1,-1,-1):
        num=a[i]
        idx=bisect_right(color,num)
        if idx==len(color):
            color.append(num)
        else:
            color[idx]=num
    
    print(len(color))    
if __name__=='__main__':
    main()
### BUGGY CODE ###

def main():
  ans = 0
  n = int(input())
  a = tuple(map(int, input().split()))
  ov = 10**9+7
  from fractions import gcd
  def lcm(a):
      x = a[0]
      ln = len(a)
      for i in range(1, ln):
          x = (x * a[i]) // gcd(x, a[i])
      return x
  l = lcm(a)
  for i in range(n):
    ans += l//a[i]%ov
  print(ans%ov)
if __name__ == "__main__":
  main()



### FIXED CODE ###

def main():
  from functools import reduce
  from fractions import gcd
  ans = 0
  n = int(input())
  b = tuple(map(int, input().split()))
  ov = 10**9+7
  def lcm(x,y):
    return (x * y) // gcd(x, y)
  def lcm_list(a):
    return reduce(lcm, a, 1)
  l = lcm_list(b)
  for i in range(n):
    ans += l//b[i]
  print(ans%ov)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys, copy
input = sys.stdin.readline

s = input().strip()
n = len(s)
mod = 10**9+7
dp = [0] * 13
mul = 1

if s[-1] == "?":
    for i in range(10):
        dp[i] = 1
else:
    dp[int(s[-1])] = 1

for i in range(2, n + 1):
    next_dp = [0]*13
    mul *= 10

    if s[-i] == "?":
        for j in range(10):
            rem = (j * mul) % 13
            for k in range(13):
                if dp[k] != 0:
                    a = (k + rem) % 13
                    next_dp[a] += dp[k]
    else:
        rem = (int(s[-i]) * mul) % 13
        for k in range(13):
            if dp[k] != 0:
                a = (k + rem) % 13
                next_dp[a] += dp[k]
    dp = copy.deepcopy(next_dp)
print(int(dp[5] % mod))

### FIXED CODE ###

def main():
  M=10**9+7
  r=tuple(tuple((j-k)*9%13for j in range(10))for k in range(13))
  d=[1]+[0]*12
  for c in input():
    if c>'9':
      d=[sum(d[j]for j in k)%M for k in r]
    else:
      d=[d[(int(c)-k)*9%13]for k in range(13)]
  print(d[5])
main()
### BUGGY CODE ###

def prime(x):
    for i in range(2, int(x**0.5+1)):
        if x % i == 0:
            return False
    return True
q = int(input())
l, r = [], []
for _ in range(q):
    l_, r_ = map(int, input().split())
    l.append(l_)
    r.append(r_)
mi, ma = min(l), max(r)
if mi == 1: mi += 2
p = [0 for _ in range(ma)]
for i in range(mi, ma+1, 2):
    if prime(i) and prime((i+1)//2):
        p[i-1] = 1
for i in range(q):
    print(sum(p[l[i]-1:r[i]]))

### FIXED CODE ###

import itertools
n = int(input())
lr = [[int(i) for i in input().split()] for _ in range(n)]
m = 101010
p = [1]*m
p[0] = p[1] = 0
for i in range(2, m):
    if p[i] == 0: continue
    else:
        for j in range(2*i, m, i):
            p[j] = 0
a = [0]*m
for i in range(1, m, 2):
    if p[i] == p[(i+1)//2] == 1: a[i] = 1
a = list(itertools.accumulate(a))
for l, r in lr:
    print(a[r] - a[l-1])
### BUGGY CODE ###

lr=input().split()
l=int(lr[0])
r=int(lr[1])

mod=2018
for i in range(r-l):
    x=r-l-i
    for j in range(x):
        a=(l+j)*(r-i)
        b=a%2019
        if b<mod:
            mod=b

print(mod)


### FIXED CODE ###

lr=input().split()
l=int(lr[0])
r=int(lr[1])

mod=2018
for i in range(r-l):
    x=r-l-i
    if mod==0:
        break
    for j in range(x):
        if (l+j)%2019==0 or (r-i)%2019==0:
            mod=0
            break
        else:
            a=(l+j)*(r-i)
            b=a%2019
            if b<mod:
                mod=b

print(mod)
### BUGGY CODE ###

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



countlist=[]
S=[0]*(N+1)
for i in range(N):
    S[i+1]=(A[i]+S[i])%M


def tr(k):
    return k*(k-1)//2


countlist=[0 for i in range(M)]
check=set()


for i in range(1,N+1):
    countlist[S[i]]+=1
    check=check|{S[i]}
    
    





ANS=countlist[0]

for i in check:
    ANS+=tr(countlist[i])

print(ANS)


### FIXED CODE ###

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

S=[0]*(N+1)
for i in range(N):
    S[i+1]=(A[i]+S[i])%M


def tr(k):
    return k*(k-1)//2


countlist=dict()
check=set()


for i in range(1,N+1):
    countlist[S[i]]=countlist.get(S[i],0)+1

    
    


ANS=countlist.get(0,0)

for i in countlist.keys():
    ANS+=tr(countlist[i])



print(ANS)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
C = []
for i in A:
    count = A.count(i) - 1
    C.append(count)

#print(C)
pre_ans = sum(C)//2
for i in range(N):
    print(pre_ans - C[i])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
X = [0]*N

for i in A:
    X[i-1] += 1

cnt = 0
for i in X:
    cnt += i* (i-1) // 2

for i in A:
    ans = cnt - (X[i-1] - 1)
    print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
contain_one = [[i, j] for i, j in ab if i == 1]

for a, b in contain_one:
    second = b
    for c, d in ab:
        if c == second:
            if d == n:
                print("POSSIBLE")
                exit()
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

n, m = map(int, input().split())
ab = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ab.append(b)
    if b == n:
        ab.append(a)

if len(ab) != len(set(ab)):
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

from math import ceil

INF = float('inf')

def minAB(x, y):
    return x if x <= y else y


N, X = map(int, input().split())
xs = list(map(int, input().split()))

maxGs = [ceil(X / (2 * x)) for x in xs]

cost0 = 5 * sum(xs) + 2 * N * X

dp2 = {(1, tuple([0, 1] + [0] * (N - 1))): cost0}
for x, maxG in zip(reversed(xs[:-1]), reversed(maxGs[:-1])):
    dp1 = {}
    for (iMin, nums), cost in dp2.items():
        # 帰り道に便乗しない場合
        num2s = list(nums)
        num2s[1] += 1
        num2s = tuple(num2s)
        dp1[(1, num2s)] = minAB(dp1.get((1, num2s), INF), cost)

        # 帰り道に便乗する場合
        if iMin <= maxG:
            iMin0 = iMin
            nums = list(nums)
            nums[iMin] -= 1
            nums[iMin + 1] += 1
            nums = tuple(nums)
            if nums[iMin] == 0:
                iMin += 1
            dp1[(iMin, nums)] = minAB(dp1.get((iMin, nums), INF), cost - X + (2 * iMin0 - 2) * x)

    dp2 = dp1

print(min(dp2.values()))


### FIXED CODE ###

from itertools import accumulate
from math import ceil

N, X = map(int, input().split())
xs = list(map(int, input().split()))

accXs = [0] + list(accumulate(reversed(xs)))

# ロボット台数kを全て試す
ans = float('inf')
for k in range(1, N + 1):
    cost = (N + k) * X

    # i番目に拾うゴミについて、追加コストをまとめて計算する
    cost += 5 * (accXs[k] - accXs[0])

    m = ceil(N / k)
    for i in range(2, m):
        cost += (2 * i + 1) * (accXs[i * k] - accXs[(i - 1) * k])

    cost += (2 * m + 1) * (accXs[N] - accXs[(m - 1) * k])

    ans = min(ans, cost)

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

n, k = map(int, input().split())
h = list(map(int, input().split()))
def chmin(a, b):
    if a > b:
        return b
    else:
        return a

dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
    for j in range(1, min(k+1, i+1)):
        dp[i] = chmin(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
def chmin(a, b):
    if a > b:
        return b
    else:
        return a

dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
    for j in range(1, min(k+1, i+1)):
        dp[i] = chmin(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

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

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

print(res)


### FIXED CODE ###

n = int(input())
res = 1
for i in range(0,n):
    res *= (i+1)
    if res > 10**9+7:
        res = res % (10**9+7)
print(res)