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

from collections import defaultdict, deque
n,m = list(map(int, input().split()))

d = defaultdict(list)

for _ in range(m):
    
    a,b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)
    
   
def dfs(node):
    
    s = set()
    stack = deque([node])
    while stack:
        
        n = stack.popleft()
        s.add(n)
        for i in d[n]:
            if i not in s and i not in visited:
                stack.append(i)
                
    return s
    
visited = set()
ans = 1

for key in list(d.keys()):
    if key not in visited:
        s = dfs(key)
        ans = max(ans, len(s))
        for i in s:
            visited.add(i)


print(ans)
        

### FIXED CODE ###

from collections import defaultdict, deque
n,m = list(map(int, input().split()))

d = defaultdict(set)

for _ in range(m):
    
    a,b = list(map(int, input().split()))
    d[a].add(b)
    d[b].add(a)
    
visited = set()

def dfs(node):
    
    c = 0
    stack = deque([node])
    visited.add(node)
    while stack:
        n = stack.popleft()
        c+=1
        for i in d[n]:
            if  i not in visited:
                visited.add(i)
                stack.append(i)
                
    return c
    

ans = 1

for key in list(d.keys()):
    if key not in visited:

        c = dfs(key)
        ans = max(ans, c)
        


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

from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
a = LIST()
b = [LIST() for i in range(m)]

c = []
for i in range(m):
    c += [b[i][1]]*b[i][0]

a += c
a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
aa = Counter(LIST())
aa = sorted(aa.items(), key=itemgetter(0))
a = [[aa[i][1], aa[i][0]] for i in range(len(aa))]
b = sorted([LIST() for i in range(m)], key=itemgetter(1), reverse=True)

ans = 0
i = j = 0
while i < len(b) and j < len(a) and b[i][1] > a[j][1]:
    if b[i][0] >= a[j][0]:
        ans += b[i][1]*a[j][0]
        b[i][0] -= a[j][0]
        a[j][0] = 0
        j += 1
    else:
        ans += b[i][1]*b[i][0]
        a[j][0] -= b[i][0]
        b[i][0] = 0
        i += 1
reg = j
if reg < len(a):
    for i in range(j, len(a)):
        ans += a[i][0]*a[i][1]
print(ans)
### BUGGY CODE ###

from collections import Counter

N, X, Y = map(int, input().split())
X -= 1
Y -= 1

ans = []

for k in range(N - 1):
    c = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            d1 = abs(j - i)
            d2 = abs(X - i) + 1 + abs(j - Y)
            d3 = abs(Y - i) + 1 + abs(j - X)
            dist = min(d1, d2, d3) - 1
            if dist == k:
                c += 1
    ans.append(c)

[print(ans[i]) for i in range(N - 1)]


### FIXED CODE ###

import numpy as np

N, X, Y = map(int, input().split())
X -= 1
Y -= 1

ans = [0] * (N-1)

for i in range(N - 1):
    for j in range(i + 1, N):
        d1 = abs(j - i)
        d2 = abs(X - i) + 1 + abs(j - Y)
        ans[min(d1, d2) - 1] += 1

[print(ans[i]) for i in range(N - 1)]
### BUGGY CODE ###

N = int(input())

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

P = [0] + P
P_ = [0] * len(P)
     
count = 0
for i in range(1, N+1):
    P_[P[i]] = 1
    if sum(P_[:P[i]]) > 0:
        continue
    count += 1
    if P[i] == 1:
        break

print(count)

### FIXED CODE ###

N = int(input())

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

P = [0] + P
     
count = 0
min = 10000000000000
for i in range(1, N+1):
    if min > P[i]:
        min = P[i]
    elif min < P[i]:
        continue
    """
    for j in range(1, i+1):
        #print(i, P[i], j , P[j])
        if P[i] > P[j]:
            #print("out", i)
            break
    else:
        #print("ok", i)
        count += 1
    """
    count += 1
        
    if P[i] == 1:
        break

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

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
maxxy = -10**9
for i in range(2**n):
    s = '0'*n + format(i, 'b')
    sl = list(s)
    #print(s)
    xy = 0
    for j in range(n):
        a = sl.pop(-1)
        if a == '1':
            xy += v[j]
            xy -= c[j]
    if xy > maxxy:
        maxxy = xy
        #print(s)
print(maxxy)

### FIXED CODE ###

import itertools as itr 

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
maxxy = -10**9
for i2 in itr.product((0,1), repeat = n):
    xy = 0
    for j in range(n):
        if i2[j] == 1:
            xy += v[j]
            xy -= c[j]
    if xy > maxxy:
        maxxy = xy
        #print(s)
print(maxxy)
### BUGGY CODE ###

def solver():
    N,W = map(int,input().split())
    item = []
    V_MAX = 0
    for _ in range(N):
        w, v = map(int,input().split())
        V_MAX += v
        item.append([w,v])
    dp = [float('inf')]*(V_MAX+1)
    dp[0] = 0
    pos = [0]
    for w,v in item:
        pos_temp = pos.copy()
        for p in pos:
            pos_temp.append(p)
            if (dp[p]+w <= W):
                dp[p+v] = min(dp[p+v], dp[p]+w)
                pos_temp.append(p+v)
        pos = pos_temp
    res = 0
    for i in range(V_MAX + 1):
        if dp[i]<=W and res < i : res = i
    print(res)

solver()

### FIXED CODE ###

import numpy as np

N,W = map(int,input().split())
item = []
V_MAX = 0
for _ in range(N):
    w, v = map(int,input().split())
    V_MAX += v
    item.append([w,v])
dp = np.array([float('inf')]*(V_MAX+1))
dp[0] = 0
pos = np.array([0]*(V_MAX+1))
pos[0] = 1
for w,v in item:
    dp = np.minimum(dp, np.concatenate([np.array([np.inf]*v),np.roll(dp,v)[v:]]) + np.dot(np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]),w))
    pos = (pos + np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]))
    pos[pos > 0] = 1
res = 0
for i in range(V_MAX + 1):
    if dp[i]<=W and res < i : res = i
print(res)
### BUGGY CODE ###

N = int(input())
nums = input().split()
mul = int(nums[0])
for i in nums[1:]:
    mul *= int(i)
if mul > 10**18:
    mul = -1
print(mul)

### FIXED CODE ###

N = int(input())
nums = input().split()
mul = int(nums[0])
if str(0) in nums:
    mul = 0
else:
    for i in nums[1:]:
        mul *= int(i)
        if len(str(mul)) >= 19 and str(mul) != "1000000000000000000":
            mul = -1
            break
print(mul)
### BUGGY CODE ###

num=int(input().rstrip())
m=input().rstrip().split()
main=[]
for i in m:
    main.append(int(i))
sample=sorted(main,reverse=True)
new=[]
result=0
for i in range(num):
    if len(new)==0:
        new.append(sample[i])
    elif len(new)<=2:
        new.append(sample[i])
        result+=sample[i-1]
    else:
        plus=new[len(new)-1]
        point=len(new)
        for j in range(len(new)-1):
            if plus<new[j] and plus<new[j+1]:
                plus=min([new[j],new[j+1]])
                point=j+1
        result+=plus
        if point==len(new):
            new.append(sample[i])
        elif point==len(new)-1:
            new.append(new[len(new)-1])
            new[len(new)-1]=sample[i]
        else:
            new.append(new[len(new)-1])
            for k in range(len(new)-1,point,-1):
                new[k]=new[k-1]
            new[point]=sample[i]
print(result)


### FIXED CODE ###

num=int(input().rstrip())
m=input().rstrip().split()
main=[]
for i in m:
    main.append(int(i))
sample=sorted(main,reverse=True)
result=0
for i in range(2,num+1):
    if i%2==0:
        y=i/2-1
        result+=sample[int(y)]
    else:
        y=(i+1)/2-1
        result+=sample[int(y)]
print(result)
### BUGGY CODE ###

import math

n, d, a = map(int,input().split())
xh = []
for i in range(n):
    x,h = map(int,input().split())
    xh.append([x,h])

num = 0
xh.sort(key=lambda xh:xh[0])
l = len(xh)
dam = [0]*n

for i in range(n):
    res = xh[i][1]-dam[i]
    if res > 0:
        nat = math.ceil(res/a)
        pos = xh[i][0]+d
        num += nat
        for j in range(n):
            if math.fabs(xh[j][0]-pos) <= d:
                dam[j] += a*nat

print(num)


### FIXED CODE ###

import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
left = [i for i in range(n)]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh.sort(key=lambda xh:xh[0])

for i in range(n):
    for j in range(left[i-1],i):
        if xh[j][0]+d >= xh[i][0]-d:
            left[i] = j
            break

dam = [0]*n

def dsum(k):
    if k == 0:
        return 0
    elif left[k] == 0:
        return dam[k-1]
    else:
        return dam[k-1]-dam[left[k]-1]

for i in range(n):
    res = xh[i][1]-dsum(i)
    nat = max([math.ceil(res/a),0])
    dam[i] = dam[i-1]+a*nat
    if res > 0:
        num += nat

print(num)
### BUGGY CODE ###

n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if 2*j - i <= n - 1:
            #k = 2*j - i
            if s[i] != s[j] and s[j] != s[2*j - i] and s[i] != s[2*j - i]:
                cnt += 1
print(R*G*B - cnt)

### FIXED CODE ###

n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if j - i <= n - 1 - j:
            if s[i] != s[j] and s[j] != s[2*j - i] and s[i] != s[2*j - i]:
                cnt += 1
print(R*G*B - cnt)
### BUGGY CODE ###

#左からn個目でendが特定の色の場合に
N,M,K = list(map(int,input().split()))

def xgcd(a, b):
  x0, y0, x1, y1 = 1, 0, 0, 1
  while b != 0:
    q, a, b = a // b, b, a % b
    x0, x1 = x1, x0 - q * x1
    y0, y1 = y1, y0 - q * y1
  return a, x0, y0
def modinv(a, m):
  g, x, y = xgcd(a, m)
  if g != 1:
    raise Exception('modular inverse does not exist')
  else:
    return x % m
def combination(n, k, mod=1e9+7) -> int:
  ret = 1
  for i in range(1, k+1):
    ret = (ret * (n-k+i) * modinv(i, mod))%mod
  return int(ret)

def pow(base, exponent, mod=1e9+7) -> int:
  if exponent == 0:
    return 1
  if exponent > 1:
    d,m = divmod(exponent, 2)
    return (base**m * pow(base, d, mod)**2 ) % mod
  else:
    return base

m = 998244353
res = 0
B = 1
if M != 1:
  mi = modinv(M-1,m)
else:
  mi = 0
A = M * pow(M-1,N-1,m)
for k in range(K+1):
  if k>0:
    B = B*(N-k)//k 
  res = (res+ A*B)%m
  A = (A*mi)%m
print (res)


### FIXED CODE ###

#左からn個目でendが特定の色の場合に
N,M,K = list(map(int,input().split()))

def xgcd(a, b):
  x0, y0, x1, y1 = 1, 0, 0, 1
  while b != 0:
    q, a, b = a // b, b, a % b
    x0, x1 = x1, x0 - q * x1
    y0, y1 = y1, y0 - q * y1
  return a, x0, y0
def modinv(a, m):
  g, x, y = xgcd(a, m)
  if g != 1:
    raise Exception('modular inverse does not exist')
  else:
    return x % m
def combination(n, k, mod=1e9+7) -> int:
  ret = 1
  for i in range(1, k+1):
    ret = (ret * (n-k+i) * modinv(i, mod))%mod
  return int(ret)

def pow(base, exponent, mod=1e9+7) -> int:
  if exponent == 0:
    return 1
  if exponent > 1:
    d,m = divmod(exponent, 2)
    return (base**m * pow(base, d, mod)**2 ) % mod
  else:
    return base

m = 998244353
res = 0
B = 1
if M != 1:
  mi = modinv(M-1,m)
  A = M * pow(M-1,N-1,m)
  for k in range(K+1):
    if k>0:
      B = (B*(N-k)*modinv(k,m))%m
    res = (res+ A*B)%m
    A = (A*mi)%m
  print (res)
else:
  if K == N-1:
    
    print(1)
  else:
    print(0)
### BUGGY CODE ###

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

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += num_list[i] * num_list[j] % (10**9 + 7)
        if ans >= (10**9 + 7):
            ans -= (10**9 + 7)

print(ans)

### FIXED CODE ###

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

list_sum = sum(num_list)

ans = 0
for i in range(N-1):
    list_sum -= num_list[i]
    ans += num_list[i] * list_sum

print(ans % (10**9 + 7))
### BUGGY CODE ###

n=int(input())
x=list(map(int, input().split()))
ll=(len(x)-1)//2

for i in range(n):
    xx=x.copy()
    del xx[i]
    xx=sorted(xx,reverse=True)
    print(xx[ll])

### FIXED CODE ###

n=int(input())
x=list(map(int, input().split()))
xx=sorted(x,reverse=True)
ll=(len(x)-1)//2
for i in range(n):
    if x[i]<xx[ll]:
        print(xx[ll])
    else:
        print(xx[ll+1])
### BUGGY CODE ###

s = input()[::-1]
words = [w[::-1] for w in ['dream', 'dreamer', 'erase', 'eraser']]
cpos = 0
while True:
  for b in words:
    pos = s.find(b)
    if pos == cpos:
      cpos += len(b)
      break
  if cpos == len(s):
    print('YES')
    break
  elif pos == -1:
    print('NO')
    break

### FIXED CODE ###

s = input().replace('eraser',"").replace('erase',"").replace('dreamer',"").replace('dream',"")
print(['YES','NO'][0<len(s)])
### BUGGY CODE ###

from collections import defaultdict
from itertools import product

INF = float('inf')

def floyd_warshall(V, E):
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for (i, j) in E[v]: dist[v][(i, j)] = 1
    for k in V:
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    for v in V:
        if dist[v][v] < 0: return None
    return dist


H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = defaultdict(list)
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.': E[(i, j)].append((x, y)); E[(x, y)].append((i, j))
dist = floyd_warshall(V, E)
ans = 0
for D in dist.values():
    for d in D.values():
        if d != INF:
            ans = max(d, ans)
print(ans)

### FIXED CODE ###

from collections import deque
from itertools import product

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))

def bfs(s):
    q = deque([(s, 0)])
    dist = {v: -1 for v in V}
    while q:
        v, d = q.popleft()
        if dist[v] >= 0: continue
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                q.append((u, d+1))
    return dist

ans = 0
for v in V:
    dist = bfs(v)
    ans = max(ans, max(dist.values()))
print(ans)
### BUGGY CODE ###

import bisect


def main():
    n = input()
    aa = []
    xx = [-input()]
    for _ in xrange(n - 1):
        aa.append(-input())
    for a in aa:
        if a >= xx[-1]:
            xx.append(a)
        else:
            i = bisect.bisect_right(xx, a)
            if i == len(xx):
                i -= 1
            xx[i] = a
    print len(xx)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect
 
 
def main():
    n = input()
    aa = []
    xx = [-input()]
    for _ in xrange(n - 1):
        aa.append(-input())
    for a in aa:
        if a >= xx[-1]:
            xx.append(a)
        else:
            i = bisect.bisect_right(xx, a)
            if i == len(xx):
                i -= 1
            xx[i] = a
    print len(xx)
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
 
f_i = sys.stdin
 
n, q = map(int, f_i.readline().split())
 
S = set([frozenset([i]) for i in range(n)])
 
def unite(sets, v1, v2):
    s1 = None
    s2 = None
    t_s = {v1, v2}
    for s in sets:
        if t_s <= s:
            return None
        elif v1 in s:
            s1 = s
        elif v2 in s:
            s2 = s
        if s1 and s2:
            break
    sets.discard(s1)
    sets.discard(s2)
    s3 = s1.union(s2)
    sets.add(s3)
 
def same(sets, v1, v2):
    for s in sets:
        t_s = {v1, v2}
        if t_s <= s:
            print(1)
            break
        elif v1 in s or v2 in s:
            print(0)
            break
 
for l in f_i:
    com, x, y = map(int, l.split())
    if com == 0:
        unite(S, x, y)
    else:
        same(S, x, y)

### FIXED CODE ###

import sys
 
f_i = sys.stdin
 
n, q = map(int, f_i.readline().split())

class DisjointSets:
    def __init__(self, size):
        # negative values are roots(representatives of each tree)
        # positive values represent the parent element
        self.table = [-1 for _ in range(size)]

    def _find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self, x, y):
        s1 = self._find(x)
        s2 = self._find(y)
        if s1 != s2:
            if self.table[s1] < self.table[s2]: # the smaller has more elements
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2

    def isSameSet(self, x, y):
        if self._find(x) == self._find(y):
            print(1)
        else:
            print(0)

S = DisjointSets(n)

for l in f_i:
    com, x, y = map(int, l.split())
    if com == 0:
        S.union(x, y)
    else:
        S.isSameSet(x, y)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import itertools


def mostProperComb(childs, x):
    tmp_sum = sum([c[1] for c in childs])
    if tmp_sum > x:
        print("IMPOSSIBLE")
        exit()

    total = tmp_sum + sum([c[0] for c in childs])

    max_a, min_b = 0, 0
    for code in itertools.product([True, False], repeat=len(childs)):
        a = 0
        for j, bool in enumerate(code):
            if bool:
                a += childs[j][1]
            else:
                a += childs[j][0]
        if a >= max_a and x >= a:
            max_a, min_b = a, total - a
            if max_a == x:
                break

    return (tuple(sorted([x, min_b], reverse=True)))


n = int(input())

p_list = [0] + list(map(int, input().split()))
x_list = list(map(int, input().split()))
c_list = [[] for i in range(n)]

if n == 1:
    print("POSSIBLE")
    exit()

for i in range(n):
    index = n - 1 - i

    if len(c_list[index]) == 0:
        c_list[index] = (x_list[index], 0)
        c_list[p_list[index] - 1].append(index)
    else:
        childs = [c_list[child_index] for child_index in c_list[index]]
        c_list[index] = mostProperComb(childs, x_list[index])
        if not p_list[index] == 0:
            c_list[p_list[index] - 1].append(index)

print("POSSIBLE")


### FIXED CODE ###

# -*- coding: utf-8 -*-

import itertools


def mostProperComb(childs, x):
    tmp_sum = sum([c[1] for c in childs])
    if tmp_sum > x:
        print("IMPOSSIBLE")
        exit()

    total = tmp_sum + sum([c[0] for c in childs])

    sset = set([tmp_sum])
    for child in childs:
        rest = child[0] - child[1]
        tmp_set = set(sset)
        for s in sset:
            if s + rest <= x:
                tmp_set.add(s+rest)
        sset = tmp_set

    return (tuple(sorted([x, total-max(sset)], reverse=True)))


n = int(input())

p_list = [0] + list(map(int, input().split()))
x_list = list(map(int, input().split()))
c_list = [[] for i in range(n)]

if n == 1:
    print("POSSIBLE")
    exit()

for i in range(n):
    index = n-1-i

    if len(c_list[index]) == 0:
        c_list[index] = (x_list[index], 0)
        c_list[p_list[index]-1].append(index)
    else:
        childs = [c_list[child_index] for child_index in c_list[index]]
        c_list[index] = mostProperComb(childs, x_list[index])
        if not p_list[index] == 0:
            c_list[p_list[index]-1].append(index)

print("POSSIBLE")
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
for _ in range(m):
    b,c = map(int,input().split())
    a = a + [c]*b
a = sorted(a,reverse = True)
a = a[:n]
print(sum(a))


### FIXED CODE ###

from operator import itemgetter
n,m = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a,reverse = True)
x = []
for _ in range(m):
    b,c = map(int,input().split())
    x.append([c,b])
x.sort(key = itemgetter(0),reverse = True)
i=0
j=0
#print(a,x)
s=0
p = 0
x1 = len(x)
while p<n:
    if (j == x1) or (a[i]>x[j][0]):
        s+=a[i]
        p+=1
        i+=1
    else:
        if (p + x[j][1]) > n:
            temp = n - p
            p+=temp
            s = s + x[j][0]*temp
        else:
            p = p + x[j][1]
            s = s + x[j][0]*x[j][1]
        #print(y)
        j+=1
print(s)
### BUGGY CODE ###

N = int( input() )
s_list = [ int(i) for i in input().split() ]
for i in range( 1, N+1):
    print(s_list.index(i)+1,end=" ")

### FIXED CODE ###

N = int( input() )
s_list = [ int(i) for i in input().split() ]
b = [0] * (10**5)
for i in range( N ):
    b[s_list[i]-1] = i + 1
for i in b:
    if i == 0:
        break
    else:
        print(i,end = " ")
### BUGGY CODE ###

N, M = map(int, input().split())
ans = set(range(1, N+1))

for i in range(M):
    l, r = map(int, input().split())
    ans &= set(range(l, r+1))

print(len(ans))

### FIXED CODE ###

N, M = map(int, input().split())
ans = set(range(1, N+1))
l_max = 1
r_min = N

for i in range(M):
    l, r = map(int, input().split())
    l_max = max(l_max, l)
    r_min = min(r_min, r)

print(max(0, r_min - l_max + 1))
### BUGGY CODE ###

S = input()
ans = 0
s = S
while s.find('BW') > -1:
    ans = ans + 1
    s = s.replace('BW', 'WB', 1)

print(ans)


### FIXED CODE ###

def solve(s):
    ans = 0
    d = 0
    sl = len(s)
    for i in range(sl):
        if s[i] == "B":
            ans = ans + (sl - i - 1 - d)
            d = d + 1
    return ans


print(solve(input()))
### BUGGY CODE ###

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    n = int(input())
    mod = 10**9+7
    power=1

    for i in range(1,n+1):
        power*=i%mod
    print(power%mod)

if __name__=="__main__":
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-

import math

def main():
    n = int(input())
    ans =math.factorial(n)
    print(ans%1000000007)

if __name__=="__main__":
    main()