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

def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    K = int(input())
    S = len(input().strip())
    mod = 10 ** 9 + 7
    fact = [1] * (K + S + 1)
    invfact = [1] * (K + S + 1)
    for i in range(K + S):
        fact[i+1] = (fact[i] * (i+1)) % mod
    invfact[-1] = pow(fact[-1], mod-2, mod)
    for i in range(K + S):
        invfact[-2-i] = (invfact[-1-i] * (K + S - i)) % mod
    def nCr(n, r):
        if r == n or r == 0:
            return 1
        r = min(r, n - r)
        return (fact[n] * invfact[n-r] * invfact[r]) % mod
    
    ans = 0
    for i in range(K+1):
        ans += pow(25, i, mod) * nCr(i+S-1, S-1) * pow(26, K-i, mod)
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    K = int(input())
    S = len(input().strip())
    mod = 10 ** 9 + 7
    fact = [1] * (K + S + 1)
    invfact = [1] * (K + S + 1)
    for i in range(K + S):
        fact[i+1] = (fact[i] * (i+1)) % mod
    invfact[-1] = pow(fact[-1], mod-2, mod)
    for i in range(K + S):
        invfact[-2-i] = (invfact[-1-i] * (K + S - i)) % mod
    def nCr(n, r):
        if r == n or r == 0:
            return 1
        r = min(r, n - r)
        return (fact[n] * invfact[n-r] * invfact[r]) % mod
    
    ans = 0
    for i in range(K+1):
        ans += pow(25, i, mod) * nCr(i+S-1, S-1) * pow(26, K-i, mod)
        ans %= mod

    print(ans)

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

import queue

H, W = list(map(int, input().split()))
ans = H * W
L = []
for i in range(H):
	s = list(input())
	ans -= s.count("#")
	L.append(s)

length = [[float("inf") for i in range(W)] for j in range(H)]
length[0][0] = 0

def breadth(H, W, q, L, length, goal):
	while True:
		m = q.get()
		x = m[0]
		y = m[1]
		if [x, y] == goal:
			break

		if y - 1 >= 0:
			if length[y - 1][x] > length[y][x] + 1:
				if L[y - 1][x] == ".":
					length[y - 1][x] = length[y][x] + 1
					q.put([x, y - 1])
		if y + 1 <= H - 1:
			if length[y + 1][x] > length[y][x] + 1:
				if L[y + 1][x] == ".":
					length[y + 1][x] = length[y][x] + 1
					q.put([x, y + 1])
		if x - 1 >= 0:
			if length[y][x - 1] > length[y][x] + 1:
				if L[y][x - 1] == ".":
					length[y][x - 1] = length[y][x] + 1
					q.put([x - 1, y])
		if x + 1 <= W - 1:
			if length[y][x + 1] > length[y][x] + 1:
				if L[y][x + 1] == ".":
					length[y][x + 1] = length[y][x] + 1
					q.put([x + 1, y])
	return length[-1][-1]

q = queue.Queue()
q.put([0, 0])
goal = [W - 1, H - 1]
goal_len = breadth(H, W, q, L, length, goal)

if length[H - 1][W - 1] == float("inf"):
	print(-1)
else:
	print(ans - goal_len - 1)


### FIXED CODE ###

import queue

H, W = list(map(int, input().split()))
ans = H * W
L = []
for i in range(H):
	s = list(input())
	ans -= s.count("#")
	L.append(s)

length = [[float("inf") for i in range(W)] for j in range(H)]
length[0][0] = 0

def breadth(H, W, q, L, length, goal):
	while not q.empty():
		m = q.get()
		x = m[0]
		y = m[1]
		if [x, y] == goal:
			break

		if y - 1 >= 0:
			if length[y - 1][x] > length[y][x] + 1:
				if L[y - 1][x] == ".":
					length[y - 1][x] = length[y][x] + 1
					q.put([x, y - 1])
		if y + 1 <= H - 1:
			if length[y + 1][x] > length[y][x] + 1:
				if L[y + 1][x] == ".":
					length[y + 1][x] = length[y][x] + 1
					q.put([x, y + 1])
		if x - 1 >= 0:
			if length[y][x - 1] > length[y][x] + 1:
				if L[y][x - 1] == ".":
					length[y][x - 1] = length[y][x] + 1
					q.put([x - 1, y])
		if x + 1 <= W - 1:
			if length[y][x + 1] > length[y][x] + 1:
				if L[y][x + 1] == ".":
					length[y][x + 1] = length[y][x] + 1
					q.put([x + 1, y])
	return length[-1][-1]

q = queue.Queue()
q.put([0, 0])
goal = [W - 1, H - 1]
goal_len = breadth(H, W, q, L, length, goal)

if length[H - 1][W - 1] == float("inf"):
	print(-1)
else:
	print(ans - goal_len - 1)
### BUGGY CODE ###

from bisect import bisect
n=int(input())
p=list(map(int,input().split()))
p=[0]+p
q=[0]*(n+1)
for i in range(1,n+1):
    q[p[i]]=i
lst=[0,q[n],n+1]
ans=0
for i in range(1,n):
    k=i
    i=n-i
    num=q[i]
    a=bisect(lst,num)
    if a==1:
        ans+=i*num*(lst[2]-lst[1])
        lst=[0,num]+lst[1:]
    elif a==1+k:
        ans+=i*(n+1-num)*(lst[k]-lst[k-1])
        lst=lst[:1+k]+[num,n+1]
    else:
        b=lst[a-2]
        c=lst[a-1]
        d=lst[a]
        e=lst[a+1]
        ans+=i*(d-num)*(c-b)+i*(num-c)*(e-d)
        lst=lst[:a]+[num]+lst[a:]
print(ans)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)
### BUGGY CODE ###

N = int(input())
P = 1
for i in range(1, N+1):
  P *= i
print(P%(10**9+7))

### FIXED CODE ###

N = int(input())
P = 1
for i in range(1, N+1):
  P *= i
  P %= 10**9+7
print(P)
### BUGGY CODE ###

n, m = map(int, input().split())
p, y = [0] * m, [0] * m
year_list = [[] for _ in range(n)]
for i in range(m):
    p[i], y[i] = map(int, input().split())
    year_list[p[i] - 1].append(y[i])
for j in range(n):
    year_list[j].sort()
for i in range(m):
    x = year_list[p[i] - 1].index(y[i]) + 1
    print(str(p[i]).zfill(6) + str(x).zfill(6))

### FIXED CODE ###

import bisect
def index(alist, x):
    i = bisect.bisect_left(alist, x)
    if i != len(alist) and alist[i] == x:
        return i
    raise ValueError

n, m = map(int, input().split())
p, y = [0] * m, [0] * m
year_list = [[] for _ in range(n)]
for i in range(m):
    p[i], y[i] = map(int, input().split())
    year_list[p[i] - 1].append(y[i])
for j in range(n):
    year_list[j].sort()
for i in range(m):
    x = index(year_list[p[i] - 1], y[i]) + 1
    print(str(p[i]).zfill(6) + str(x).zfill(6))
### BUGGY CODE ###

import numpy as np
#import math
N, K = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
F = np.array(sorted(list(map(int, input().split())), reverse=True))

C = A*F

left = - 1
right = 10**12

def f(x):
    return sum(np.maximum(0, A - x//F)) <= K

while right - left > 1:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid
    
print(right)

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
F = np.array(sorted(list(map(int, input().split())), reverse=True))

left = - 1
right = 10**12

def f(x):
    return np.maximum(0, A - x//F) .sum()<= K

while right - left > 1:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid
    
print(right)
### BUGGY CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():
    N,K = map(int,input().split())
    H = list(map(int,input().split()))

    dp = [0] * N
    dp[1] = abs(H[1] - H[0])
    for i in range(2,N):
        dp[i] = min(dp[i-j] + abs(H[i] - H[i-j]) for j in range(1,max(K,i)))
    print(dp[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0] * (N + 1)

    dp[0] = 0
    dp[1] = abs(h[1]-h[0])
    for i in range(2,N):
        dp[i] = min(dp[j] + abs(h[i]-h[j]) for j in range(max(0,i-K),i))
    print(dp[N-1])

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

X = int(input())
ans = 1
for i in range(2,X):
    for j in range(2,X):
        tmp_ans = i ** j
        if tmp_ans > ans and tmp_ans <= X:
            ans = tmp_ans
print(ans)

### FIXED CODE ###

X = int(input())
ans = 1
for b in range(2,X):
    for p in range(2,X):
        tmp_ans = b ** p
        if tmp_ans > X:
            break
        if tmp_ans > ans:
            ans = tmp_ans
print(ans)
### BUGGY CODE ###

from sys import stdin
from functools import lru_cache
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]


@lru_cache(None)
def dp(w: 'int', n: 'int') -> 'int':
    if w == 0 or n == 0:
        return 0
    if s[n - 1][0] > w:
        return dp(w, n - 1)
    else:
        return max(dp(w, n - 1), dp(w - s[n - 1][0], n - 1) + s[n - 1][1])


print(dp(W, N))


### FIXED CODE ###

# using dp with memoization, TLE
from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

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

for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w == 0:
            dp[n][0] = 0
            continue
        if w < s[n - 1][0]:
            dp[n][w] = dp[n - 1][w]
        else:
            dp[n][w] = max(dp[n - 1][w],
                           dp[n - 1][w - s[n - 1][0]] + s[n - 1][1])

print(dp[N][W])
### BUGGY CODE ###

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

import copy,sys

def solve(pieace):
	target_list = list(range(8))

	frontier,previous_frontier = set(),set()
	frontier.add(tuple(pieace))

	for step in range(10*10):
		next_frontier = set()
		for pieace in frontier:
			if all(x==y for x,y in zip(pieace,target_list)):	return step
			zero_position = pieace.index(0)
			relative = zero_position%4

			new_peiace = list(copy.deepcopy(pieace))
			new_peiace[relative],new_peiace[relative+4] = new_peiace[relative+4],new_peiace[relative]
			new_peiace = tuple(new_peiace)
			if new_peiace not in previous_frontier:
				next_frontier.add(new_peiace)

			if relative in [0,1,2]:
				new_peiace = list(copy.deepcopy(pieace))
				new_peiace[zero_position],new_peiace[zero_position+1] = new_peiace[zero_position+1],new_peiace[zero_position]
				new_peiace = tuple(new_peiace)
				if new_peiace not in previous_frontier:
					next_frontier.add(new_peiace)

			if relative in [1,2,3]:
				new_peiace = list(copy.deepcopy(pieace))
				new_peiace[zero_position],new_peiace[zero_position-1] = new_peiace[zero_position-1],new_peiace[zero_position]
				new_peiace = tuple(new_peiace)
				if new_peiace not in previous_frontier:
					next_frontier.add(new_peiace)

		previous_frontier = frontier
		frontier = next_frontier

def main():
	line = input().strip()
	while line!='':
		pieace = list(map(int,line.split(' ')))
		print(solve(pieace))
		line = input().strip()

if __name__=='__main__':
	main()

### FIXED CODE ###

from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input

X=4
Y=2
i=0
m={}
prev={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
prev[''.join(v)]=[''.join(v),None]
q=[v]
while len(q)>0:
	v=q.pop(0)
	coor=m[''.join(v)][0]
	x=coor%X
	y=coor//X
	depth=m[''.join(v)][1]
	nextstr=''.join(v)
	if 0<x:
		v[coor],v[coor-1]=v[coor-1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-1,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'R']
		v[coor],v[coor-1]=v[coor-1],v[coor]
	if x<X-1:
		v[coor],v[coor+1]=v[coor+1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+1,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'L']
		v[coor],v[coor+1]=v[coor+1],v[coor]
	if 0<y:
		v[coor],v[coor-X]=v[coor-X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-X,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'D']
		v[coor],v[coor-X]=v[coor-X],v[coor]
	if y<Y-1:
		v[coor],v[coor+X]=v[coor+X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+X,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'U']
		v[coor],v[coor+X]=v[coor+X],v[coor]

try:
	while True:
		v=raw_input().split()
		print(m[''.join(v)][1])
except EOFError:
	pass
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array([sorted(list(map(int, input().split()))) for _ in range(3)])
ans = 0
for i in range(n):
    ans += np.sum(a[0] < a[1][i]) * np.sum(a[2] > a[1][i])
print(ans)

### FIXED CODE ###

import bisect
ans = 0
n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))
for i in range(n):
    ans += bisect.bisect_left(a, b[i]) * (n - bisect.bisect_right(c, b[i]))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
for _ in range(k):
    lst = [0]*(n+1)
    for i in range(n):
        lst[max(i - a[i], 0)] += 1
        lst[min(i + a[i] + 1, n)] -= 1
    a = list(accumulate(lst))[:-1]

print(*list(accumulate(lst))[:-1])

### FIXED CODE ###

#!/usr/bin/env python3
 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
for _ in range(k):
    lst = [0]*(n+1)
    for i in range(n):
        lst[max(i - a[i], 0)] += 1
        lst[min(i + a[i] + 1, n)] -= 1
    a = list(accumulate(lst))[:-1]
    for i in range(n):
        if a[i] != n:
            break
    else:
        print(*a)
        quit()
print(*a)
### BUGGY CODE ###

def main():
    n=int(input())
    s=input()
    r = [0]*n
    g = [0]*n
    b = [0]*n
    ans = 0

    for i in range(n):
        s1 = s[i]
        if s1 == "R":
            r[i] = 1
        elif s1 == "G":
            g[i] = 1
        else:
            b[i] = 1
    
    dict = {"R":r, "G":g, "B":b}

    def rgb_sum(t,i,j):
        for s3 in "RGB":
            if s3 not in t:
                if 2*j-i < n:
                    return sum(dict[s3][j+1:]) - dict[s3][2*j-i]
                else:
                    return sum(dict[s3][j+1:])

    for i in range(n):
        for j in range(i,n):
            s1 = s[i]
            s2 = s[j]
            t = (s1,s2)
            if s1 != s2:
                ans += rgb_sum(t,i,j)

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n=int(input())
    s=input()
    ans = 1

    r_cnt = s.count("R")
    g_cnt = s.count("G")

    ans = r_cnt*g_cnt*(n-r_cnt-g_cnt)
 
    for i in range(n):
        for j in range(i,n):
            s1 = s[i]
            s2 = s[j]
            if s1 != s2:
                t = (s1,s2)
                for s3 in "RGB":
                    if s3 not in t:
                        if 2*j-i < n and s[2*j-i] == s3:
                            ans -= 1
                        continue

    print(ans)

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

k = input()
k = int(k)

ll = []
for i in range(1, k + 1):
    l = []
    for j in range(1, i + 1):
        if i % j == 0:
            l.append(j)
            l.append(i // j)
        if (i // j) < j:
            break
    ll.append(set(l))


sum_k = 0

for i in range(k):
    for j in range(k):
        for l in range(k):
            sum_k += max(ll[i] & ll[j] & ll[l])

print(sum_k)


### FIXED CODE ###

k = input()
k = int(k)

ll = []
for i in range(1, k + 1):
    l = []
    for j in range(1, i + 1):
        if i % j == 0:
            l.append(j)
            l.append(i // j)
        if (i // j) < j:
            break
    ll.append(set(l))


sum_k = 0

for i in range(k):
    i_s = ll[i]
    for j in range(k):
        j_s = ll[j]
        m = max(ll[i] & ll[j])
        if m == 1:
            sum_k += k
            continue
        for l in range(k):
            sum_k += max(ll[i] & ll[j] & ll[l])

print(sum_k)
### BUGGY CODE ###

import numpy as np
s = str(input())

num_list = []
for j in range(4, len(s)+1):
    for i in range(len(s)-j+1):
        num_list.append(int(s[i:j+i]))
        
print(np.where(np.array(num_list) % 2019 == 0, 1, 0).sum())

### FIXED CODE ###

s = str(input())[::-1]
sum_of_digits = 0
cnt = [0] * 2019

cnt[0] = 1
d = 1
for c in s:
    d *= 10
    d %= 2019
    sum_of_digits += d * int(c)
    sum_of_digits %= 2019
    cnt[sum_of_digits] += 1

print(sum([i*(i-1)//2 for i in cnt]))
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.buffer.readline
N = int(input())
A = np.array(list(map(int, input().split())))

# print(A.cumsum())

ans = 0
cumsum = A.cumsum()
# print(cumsum)
for _ in range(len(cumsum)):
    ans += np.count_nonzero(cumsum == 0)
    cumsum = cumsum[1:] - cumsum[0]
    # print(cumsum)
print(ans)


### FIXED CODE ###

import sys
import numpy as np
from collections import Counter
input = sys.stdin.buffer.readline
N = int(input())
A = np.array(list(map(int, input().split())))

# print(A.cumsum())

ans = 0
cumsum = A.cumsum()

# print(cumsum)

# for _ in range(len(cumsum)):
#     ans += np.count_nonzero(cumsum == 0)
#     cumsum = cumsum[1:] - cumsum[0]
#     print(cumsum)
# print(ans)

# [1 4 0 2 4 2]


# 自分より前に同じ値の数字があるか
def f(n):
    return n * (n - 1) // 2


ans = 0
for key, value in Counter(cumsum).items():
    if key == 0:
        ans += value
    if value >= 2:
        ans += f(value)
# _, counts = np.unique(cumsum, return_counts=True)
# print(counts)
# values, counts = np.unique(counts, return_counts=True)
# ans = 0
# for value, count in zip(values, counts):
#     ans += f(value) * count
print(ans)
### BUGGY CODE ###

N,C = map(int,input().split())
tv_times = [[int(j) for j in input().split()] for i in range(N)]

channells = {}
for i in range(N):
    s,g,c = tv_times[i]
    if c in channells.keys():
        channells[c] += [s,g]
    else:
        channells[c] = [s,g]

tv_times = []
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    for j in range(len(remove_list)):
        time.remove(remove_list[j])
        time.remove(remove_list[j])

    for i in range(len(time)//2):
        tv_times.append([time[2*i],time[2*i+1]])

max_end = -1
for i in range(len(tv_times)):
    max_end = max(tv_times[i][1],max_end)

count = [0 for i in range(max_end)]
for ni in range(len(tv_times)):
    for time in range(max(tv_times[ni][0]-1,0),tv_times[ni][1]):
        count[time] += 1

print(max(count))


### FIXED CODE ###

N,C = map(int,input().split())
tv_times = [[int(j) for j in input().split()] for i in range(N)]

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]

tv_times = []
f = [0 for i in range(max_end+1)]
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(1,len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    time = list(set(time)-set(remove_list))
    time.sort()
    for i in range(len(time)//2):
        f[max(time[2*i]-1,0)] += 1
        f[time[2*i+1]] -= 1
ans = -1
for i in range(1,max_end+1):
    f[i] += f[i-1]
    if ans < f[i]:
        ans = f[i]

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

R,G,B,N=map(int,input().split())
cnt=0
for i in range(N+1):
    for j in range(N+1):
        if i*R+j*G<=N and (N-(i*R+j*G))%B==0:
            cnt+=1
print(cnt)

### FIXED CODE ###

R,G,B,N=map(int,input().split())
cnt=0
for i in range(N+1):
    for j in range(N+1):
        if i*R+j*G<=N and (N-(i*R+j*G))%B==0:
            cnt+=1
print(cnt)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(k):
  add_a=[0]*(n+1)
  for i in range(n):
    a[i]
    add_a[max(0,i-a[i])]+=1
    add_a[min(n,i+a[i]+1)]-=1
  tmp=0
  for i in range(n):
    tmp+=add_a[i]
    a[i]=tmp
print(' '.join(map(str,a)))


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(min(k,int(n**0.5)+10)):
  add_a=[0]*(n+1)
  for i in range(n):
    a[i]
    add_a[max(0,i-a[i])]+=1
    add_a[min(n,i+a[i]+1)]-=1
  tmp=0
  for i in range(n):
    tmp+=add_a[i]
    a[i]=tmp
print(' '.join(map(str,a)))
### BUGGY CODE ###

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

if N == 1:
    print(1)
    exit()

def saisho_ko_baisu(A,B):
    # A < B
    if B < A:
        A,B = B,A
    x = A*B
    r = B%A
    while r!=0:
        B = A
        A = r
        r = B%A
    return x//A

A.sort()
tmp = saisho_ko_baisu(A[0], A[1])
for i in range(2,N):
    if tmp % A[i] != 0:
        tmp = saisho_ko_baisu(tmp, A[i])
res = 0
for a in A:
    res += tmp//a

print(res % (10**9 + 7))


### FIXED CODE ###

from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

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

div = 10**9 + 7
lcm_num = lcm(a)
ans = [lcm_num//ai for ai in a]

print(sum(ans)%div)
### BUGGY CODE ###

import heapq

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

heapq.heapify(change)
heapq.heapify(a)

while change:
    b, c = heapq.heappop(change)
    while a[0] < b and c > 0:
        tmp = heapq.heappop(a)
        heapq.heappush(a, b)
        c -= 1
        
print(sum(a))

### FIXED CODE ###

import heapq


change = []
n, m = map(int, input().split())
a = [-1 * int(i) for i in input().split()]
for i in range(m):
    b, c = map(int, input().split())
    change.append([-c, b])

l = []
heapq.heapify(change)
heapq.heapify(a)
flg = False
cnt = 0
while cnt < n:
    if change:
        atmp = -1 * a[0]
        btmp = -1 * change[0][0]
        if atmp <= btmp:
            b, c = heapq.heappop(change)
            while c > 0 and cnt < n:
                l.append(b)
                c -= 1
                cnt += 1
        else:
            aa = heapq.heappop(a)
            l.append(aa)
            cnt += 1
    else:
        aa = heapq.heappop(a)
        l.append(aa)
        cnt += 1
        
print(-1 * sum(l))
### BUGGY CODE ###

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

n = int(input())
ans = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            ans += gcd(gcd(i, j), k)

print(ans)


### FIXED CODE ###

from math import gcd

n = int(input())
ans = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            ans += gcd(gcd(i, j), k)
            
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


def main():
    n, q = map(int, input().split())
    e = [list(map(int, input().split())) for _ in range(n-1)]
    p = [list(map(int, input().split())) for _ in range(q)]

    e2 = [[] for _ in range(n)]
    for ee in e:
        a, b = ee
        e2[a-1].append(b-1)
        e2[b-1].append(a-1)

    counters = [0 for _ in range(n)]
    for pp in p:
        counters[pp[0]-1] += pp[1]

    used = [0] * n

    def dfs(x, p_sum):
        counters[x] += p_sum
        used[x] = 1
        for y in e2[x]:
            if used[y] == 1:
                continue
            dfs(y, counters[x])

    dfs(0, 0)
    print(*counters)


main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)


def main():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    e = [list(map(int, input().split())) for _ in range(n-1)]
    p = [list(map(int, input().split())) for _ in range(q)]

    e2 = [{} for _ in range(n)]
    for ee in e:
        a, b = ee
        e2[a-1][b-1] = 1
        e2[b-1][a-1] = 1

    counters = [0 for _ in range(n)]
    for pp in p:
        counters[pp[0]-1] += pp[1]

    def dfs(x, p_sum):
        counters[x] += p_sum
        for y in e2[x]:
            del e2[y][x]
            dfs(y, counters[x])

    dfs(0, 0)
    print(*counters)


main()
### BUGGY CODE ###

num = int(input())
result = 1
for i in range(1,num+1):
    result = result *i
print(result % 1000000007)

### FIXED CODE ###

import math
print(math.factorial(int(input()))%1000000007)