Harryxun/stf_run huggingface dataset:
X = 998244353

N, M, K = map(int, input().split())

def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

inv_cache = [1]
for i in range(1, K + 1):
	inv_cache.append(calc_inverse(i, X))

inv_f_cache = [1]
d = 1
for i in range(1, K + 1):
	d = (d * inv_cache[i]) % X
	inv_f_cache.append(d)

f_cache = [1]
c = 1
for i in range(N - 1, N - M, -1):
	c = (c * i) % X
	f_cache.append(c)

#print(f_cache, inv_f_cache)

def C(n, m):
#	if m in f_cache:
#		c = f_cache[m]
#	else:
#		c = 1
#		for i in range(n - m + 1, n + 1):
#			c = (c * i) % X
#		f_cache[m] = c
#	d = 1
#	for i in range(1, m + 1):
#		d = (d * inv_cache[i]) % X
	return (f_cache[m] * inv_f_cache[m]) % X


total = 0
for k in range(K + 1):
	total = (total + M * pow(M - 1, N - 1 - k, X) * C(N - 1, k)) % X
	
#	print(k, M * pow(M - 1, N - 1 - k, X))
	

print(total)


### FIXED CODE ###

X = 998244353

N, M, K = map(int, input().split())

def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

inv_cache = [1]
for i in range(1, K + 1):
	inv_cache.append(calc_inverse(i, X))

inv_f_cache = [1]
d = 1
for i in range(1, K + 1):
	d = (d * inv_cache[i]) % X
	inv_f_cache.append(d)

f_cache = [1]
c = 1
for i in range(N - 1, N - K - 1, -1):
	c = (c * i) % X
	f_cache.append(c)

#print(f_cache, inv_f_cache)

def C(n, m):
#	if m in f_cache:
#		c = f_cache[m]
#	else:
#		c = 1
#		for i in range(n - m + 1, n + 1):
#			c = (c * i) % X
#		f_cache[m] = c
#	d = 1
#	for i in range(1, m + 1):
#		d = (d * inv_cache[i]) % X
#	print(m)
	return (f_cache[m] * inv_f_cache[m]) % X


total = 0
for k in range(K + 1):
	total = (total + M * pow(M - 1, N - 1 - k, X) * C(N - 1, k)) % X
	
#	print(k, M * pow(M - 1, N - 1 - k, X))
	

print(total)
N, A, B = map(int, input().split())
S = list(input())
 
ok_count = 0
ok_fcount = 0
for i in range(N):
  if S[i] == a:
    if ok_count < A+B-1:
      print('Yes')
      ok_count +=1
      
    else:
      print('No')
      
  elif S[i] == b:
    if ok_count <= A+B-1 and ok_fcount < B-1:
      print('Yes')
      ok_count+=1
      ok_fcount+=1
      
    else:
      print('No')
      
  else:
    print('No')

### FIXED CODE ###

N, A, B = map(int, input().split())
S = input()
 
ok_count = 0
ok_fcount = 0
for i in range(N):
  if S[i] == 'a':
    if ok_count < A+B:
      print('Yes')
      ok_count +=1
      
    else:
      print('No')
      
  elif S[i] == 'b':
    if ok_count < A+B and ok_fcount < B:
      print('Yes')
      ok_count+=1
      ok_fcount+=1
      
    else:
      print('No')
      
  else:
    print('No')
N,M=map(int,input().split())
a=[map(int,input().split()) for i in range(N)]
a=sorted(a, reversed =True)
if sum(a)/(4*M)<=a[M-1]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N,M=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a, reverse=True)
if sum(a)/(4*M)<=a[M-1]:
  print("Yes")
else:
  print("No")
A1 = list(map(int,input().split()))
A2 = list(map(int,input().split()))
A3 = list(map(int,input().split()))
N = int(input())

for i in range(N):
    b = int(input())
    for t in range(3):
        if A1[t] == b:
            A1[t] = -1
        elif A2[t] == b:
            A2[t] = -1
        elif A3[t] == b:
            A3[t] = -1

if A1 == A2 == A3 == [-1, -1, -1] or A1[1] == A2[1] == A3[1] == -1 or A1[2] == A2[2] == A3[2] == -1　or A1[0] == A2[0] == A3[0] == -1 or A1[0] == A2[1] == A3[2] == -1 or A1[2] == A2[1] == A3[0] == -1:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

A1 = list(map(int,input().split()))
A2 = list(map(int,input().split()))
A3 = list(map(int,input().split()))
N = int(input())

for i in range(N):
    b = int(input())
    for t in range(3):
        if A1[t] == b:
            A1[t] = -1
        elif A2[t] == b:
            A2[t] = -1
        elif A3[t] == b:
            A3[t] = -1

if A1 == [-1, -1, -1] \
        or A2 == [-1, -1, -1] \
        or A3 == [-1, -1, -1] \
        or A1[1] == A2[1] == A3[1] == -1 \
        or A1[2] == A2[2] == A3[2] == -1 \
        or A1[0] == A2[0] == A3[0] == -1 \
        or A1[0] == A2[1] == A3[2] == -1 \
        or A1[2] == A2[1] == A3[0] == -1 \
        or A1[0] == A2[0] == A3[0] == -1 \
        or A1[1] == A2[1] == A3[1] == -1 \
        or A1[2] == A2[2] == A3[2] == -1:
    print('Yes')
else:
    print('No')
def gcd(a,b):
    if a>b :
        while b!=0:
            a,b = b,a%b
        return a
    elif a==b:
        return a
    else :
        while a!=0:
            a,b = b%a,a
        return b

def lcm(n,A):
    gcdn = [0]*n
    lcmn = [0]*n

    gcdn[0]=A[0]
    lcmn[0]=A[0]
    for i in range(n-1):
        gcdn[i+1] = gcd(lcmn[i],A[i+1])
        M = lcmn[i]*A[i+1]
        lcmn[i+1] =int(M/gcdn[i+1])
    return lcmn[n-1]


def examC():
    N = I()
    T = [I() for _ in range(N)]
    ans = lcm(N,T)
    print(ans)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()


### FIXED CODE ###

def gcd(x, y):
    if y == 0:
        return x
    while y != 0:
        x, y = y, x % y
    return x

def lcm(x, y):
    return x * y // gcd(x, y)


def examC():
    N = I()
    T = [I() for _ in range(N)]
    ans = 1
    for t in T:
        ans = lcm(ans, t)
    print(ans)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()
H,N map(int, input().split())
A = list(map(int, input().split()))
for Ax in A:
  H -= Ax
if H < 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

H,N =map(int, input().split())
A = list(map(int, input().split()))
for Ax in A:
  H -= Ax
if H > 0:
  print("No")
else:
  print("Yes")
A = int(input())
B = int(input())
C = int(input())

#A = str(len("a"))
#B = str(len("b"))
#C = str(len("c"))

if A == 5 and B == 5 and C == 7:
    print("YES")

elif A == 5 and B == 7 and C == 5:
    print("YES")

elif A == 7 and B == 5 and C == 7:
    print("YES")

elif A == 7 and B == 5 and C == 5:
    print("YES")
    
else:
    print("NO")


### FIXED CODE ###

a=input().split()
if a.count('5')==2 and a.count('7')==1:
    print('YES')
else:
    print('NO')
ｖn, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(n)]
inf = 10 ** 18


def dfs(i, a, b, c):
    if i == n:
        if a < 1 or b < 1 or c < 1:
            return inf
        return abs(A - a) + abs(B - b) + abs(C - c)
    res = dfs(i + 1, a, b, c)
    res = min([res, dfs(i + 1, a + l[i], b, c) + (10 if a > 0 else 0)])
    res = min([res, dfs(i + 1, a, b + l[i], c) + (10 if b > 0 else 0)])
    res = min([res, dfs(i + 1, a, b, c + l[i]) + (10 if c > 0 else 0)])
    return res


print(dfs(0, 0, 0, 0))


### FIXED CODE ###

"""
できなかった

- 操作 = 四則演算 or 関数
- 交換法則などが成り立つかどうか確認する必要がある
- 再帰的(dfs)に実装する場合、何を初期値として終了条件とするかの理解が必要
  - 前提として全探索であること => 1の解に収束する必要がない
    全ての葉を訪れたときに最小・最大値・解への到達が判定できれば良い

- dfsの実装: いまどの高さにいるかを引数として渡す = 何を高さとして定義するか
  - 階層のインデックスは選択可能な配列のインデックス
  - 同階層のノードは選択肢
  - ノードが持つ値は、その選択をした時の合計の値
  - 終了条件A, B, Cを満たす

- 求める長さA, B, Cの竹 -> 選択肢

"""
(N, A, B, C) = map(int, input().split())
l = [int(input()) for _ in range(N)]


def dfs(index, a, b, c):
    if N == index:
        if 0 < min(a, b, c):
            return abs(a - A) + abs(b - B) + abs(c - C) - 30
        else:
            return 10 ** 9
    costs = []
    costs.append(dfs(index + 1, a, b, c))
    costs.append(dfs(index + 1, a + l[index], b, c) + 10)
    costs.append(dfs(index + 1, a, b + l[index], c) + 10)
    costs.append(dfs(index + 1, a, b, c + l[index]) + 10)
    return min(costs)


print(dfs(0, 0, 0, 0))
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
lst1 = [list(map(int,readline().split())) for i in range(n)]

cost = 1

#同じベクトルでつなげる要素を最大化する。全点対象にベクトルを求め、多数決。
dic1 = dict()

for i in range(n-1):
    for j in range(i+1,n):
        x,y = lst1[i][0] - lst1[j][0] , lst1[i][1] - lst1[j][1]
        if (x,y) in dic1:
            dic1[(x,y)] += 1
        else:
            dic1[(x,y)] = 1

#線分は頂点-1個。そのうち同ベクトル数が免除される。
cost += n-1
cost -= max(dic1.values())

print(cost)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
lst1 = [list(map(int,readline().split())) for i in range(n)]
lst1.sort()
cost = 1
if n == 1:
    print(cost)
    exit()
#同じベクトルでつなげる要素を最大化する。全点対象にベクトルを求め、多数決。
dic1 = dict()

for i in range(n-1):
    for j in range(i+1,n):
        x,y = lst1[i][0] - lst1[j][0] , lst1[i][1] - lst1[j][1]
        """
        if x < 0 and y < 0:
            x,y = -x,-y
        elif x < 0 and y >= 0:
            x,y = -x,-y"""
        if (x,y) in dic1:
            dic1[(x,y)] += 1
        else:
            dic1[(x,y)] = 1

#線分は頂点-1個。そのうち同ベクトル数が免除される。
cost += n-1
cost -= max(dic1.values())

print(cost)
a, b, c, k = map(int, input().split())
if k <= a:
    k_pa, k_pb, k_pc = k , 0, 0 
elif k >= a and k-a <= b:
    k_pa, k_pb, k_pc = a, k-a, 0
elif k >= a and k-a >= b:
    k_pa, k_pb, k_pc = a, k-a, k-a-b
point = k_pa - (k-k_pa-k_pb)
print(point)

### FIXED CODE ###

s = list(input())
t = list(input())
t.pop(-1)
print('Yes' if s == t else 'No')
def include3(n):
	cond = 0
	while True:
		if n%10==3:
			cond = 1
			return cond
		elif n>9:
			n /= 10
		else:
			return cond

n = int(input())
print(' ',end='')
for i in range(i,n+1):
	if i%3==0 or include3(n)==1:
		print('%d ' % (n))


### FIXED CODE ###

def include3(n):
	cond = 0
	while True:
		if n%10==3:
			cond = 1
			return cond
		elif n>9:
			n //= 10
		else:
			return cond

n = int(input())
for i in range(1,n+1):
	if i%3==0 or include3(i)==1:
		print(' ',end='')
		print(i,end='')
print()
a = int(input())
b = int(input())
 
print(str(a*b) ,str(2a + 2b))

### FIXED CODE ###

z = input()
m,l = z.split()
s = int(m) * int(l)
n = int(m)*2 + int(l)*2

print("{} {}".format(str(s),str(n)))
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
import numpy as np
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
d1 = [] * n
d2 = [] * n

for i in range(n):
    x, y = map(int, input().split())
    d1.append(x+y)
    d2.append(x-y)

print(max(max(d1) - min(d1), max(d2)-min(d2)))


### FIXED CODE ###

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
d1 = [] * n
d2 = [] * n

for i in range(n):
    x, y = map(int, input().split())
    d1.append(x+y)
    d2.append(x-y)

print(max(max(d1) - min(d1), max(d2)-min(d2)))
n, k = list(map(int, input().split()))
s = input()
print(s[:k-1]+s[k].lower()+s[k:])


### FIXED CODE ###

n, k = list(map(int, input().split()))
s = input()

# 文字列に対してk以前とｋ以降をそのまま表示。
# kのみstr.lower()を適用する
print(s[:k-1]+s[k-1].lower()+s[k:])
def warshall_floyd(g):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])

n = int(input())
s = [[int(i) for i in list(input())] for _ in range(n)]
graph = [[float("inf")]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j] == 1:
            graph[i][j] = 1
        if i == j:
            graph[i][j] = 0

warshall_floyd(graph)
d = 0
#print(graph)
for i in range(n-1):
    for j in range(i+1,n):
        if graph[i][j] != float("inf"):
            if d < graph[i][j]:
                start = i
                end = j
                d = graph[i][j]

v = [[] for _ in range(d+1)]
for i in range(n):
    l = graph[start]
    v[l[i]].append(i)
#print(v)
#print(start,end)

for l in v:
    m = len(l)
    for i in range(m-1):
        for j in range(i+1,m):
            if s[l[i]][l[j]] == 1:
                print(-1)
                quit()
print(d+1)

### FIXED CODE ###

s = input()
k = int(input())
n = len(s)
a = []
cnt = 1
for i in range(n-1):
  if s[i] == s[i+1]:
    cnt += 1
  else:
    a.append(cnt)
    cnt = 1
if sum(a) != n:
  a.append(cnt)
m = len(a)
if m == 1:
  print((a[0]*k)//2)
  exit()
if m == 2:
  print((a[0]//2+a[1]//2)*k)
  exit()
cnt = 0
for i in range(1,m-1):
  cnt += a[i] // 2
cnt *= k
if s[0] == s[n-1]:
  cnt += (k-1)*((a[0]+a[m-1])//2)
else:
  cnt += (k-1)*(a[0]//2+a[m-1]//2)
cnt += a[0]//2 + a[m-1]//2
print(cnt)
N, M = map(int, input().split())
numbers = set(map(int, input().split()))
costs = [2,5,5,4,5,6,3,7,6] # <- 1,2,3,4,5,6,7,8,9
costmap = {}
for num in numbers:
  cost = costs[num-1]
  if cost in costmap and num < costmap[cost]:
    continue
  costmap[cost] = num

from functools import lru_cache
@lru_cache(None)
def recursive(remain=N):
  maxval = costmap[remain] if remain in costmap else 0
  for cost, num in costmap.items():
    if remain > cost:
      val = recursive(remain-cost)
      if val is None:
        continue
      val = val * 10 + num
      if val > maxval:
        maxval = val
  if maxval == 0:
    return None
  return maxval

print(recursive(N))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
numbers = list(map(int, input().split()))
costs = [2,5,5,4,5,6,3,7,6] # <- 1,2,3,4,5,6,7,8,9
costmap = {}
for num in numbers:
  cost = costs[num-1]
  if cost in costmap and num < costmap[cost]:
    continue
  costmap[cost] = num

from functools import lru_cache
@lru_cache(None)
def recursive(remain=N):
  maxval = costmap[remain] if remain in costmap else 0
  for cost, num in costmap.items():
    if remain > cost:
      val = recursive(remain-cost)
      if val == 0:
        continue
      val = val * 10 + num
      if val > maxval:
        maxval = val
  return maxval
 
print(recursive(N))
S = float(input("Input seconds: "))
S = S % (24 * 3600)
hour = S // 3600
S %= 3600
minutes = time // 60
S %= 60
seconds = S
print("%d:%d:%d" % (hour, minutes, seconds))


### FIXED CODE ###

S = float(input())
S = S % (24 * 3600)
hour = S // 3600
S %= 3600
minutes = S // 60
S %= 60
seconds = S
print("%d:%d:%d" % (hour, minutes, seconds))
d = {}


def f(s, n, m, a, js):
    if s in d:
        return d[s]
    cnt = [0] * m
    for i in xrange(n):
        cnt[a[i][js[i]]] += 1
    mc = max(cnt)
    d[s] = min(mc, min(
        f(s | {k}, n, m, a, [js[i] + (1 if a[i][js[i]] == k else 0) for i in xrange(n)])
        for k in xrange(m) if cnt[k] == mc
    ))
    return d[s]


def main():
    n, m = [int(x) for x in raw_input().split()]
    a = [[int(x) - 1 for x in raw_input().split()] for i in xrange(n)]
    d[frozenset(xrange(m))] = n
    return f(frozenset(), n, m, a, [0] * n)


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def main():
    n, m = [int(x) for x in raw_input().split()]
    a = [[int(x) - 1 for x in raw_input().split()] for i in xrange(n)]
    ans = n
    for _ in xrange(m):
        cnt = [0] * m
        for ai in a:
            cnt[ai[0]] += 1
        c = max(xrange(m), key=lambda k: cnt[k])
        ans = min(ans, cnt[c])
        for ai in a:
            ai.remove(c)
    return ans


if __name__ == '__main__':
    print(main())
a,b=map(int,input().split())
	if a!=2 and b!=2:
		print("Yes")
	else:
		print("No")

### FIXED CODE ###

a,b=map(int,input().split())
if a!=2 and b!=2:
	print("Yes")
else:
	print("No")
X = int(input())
for a in range(-120,120):
  for b in range(-120,120):
    if a**5 - b**5 == X:
      print(A,B)
      exit(0)

### FIXED CODE ###

X = int(input())
for a in range(-120,120):
  for b in range(-120,120):
    if a**5 - b**5 == X:
      print(a,b)
      exit(0)
import math as m

N=input()
X=input()
T=input()

N=int(N)
X=int(X)
T=int(T)

s=N/X
s=m.ceil(s)
s=int(s)
i=s*T
print(i)

### FIXED CODE ###

import math as m

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

N=LIST[0]
X=LIST[1]
T=LIST[2]

s=N/X
s=m.ceil(s)
s=int(s)
i=s*T
print(i)
import numpy as np

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

A=[]
for i in range(N):
    A.append(list(input()))

B=[]
for j in range(M):
    B.append(list(input()))

A=np.asarray(A)
B=np.asarray(B)
flg=False
if (A == B).all():
    flg=True
  
for x in range(N-M):
    for y in range(N-M):
        if (A[x:x+M,y:y+M] == B).all():
            flg=True
if flg:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import numpy as np

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

A=[]
for i in range(N):
    A.append(list(input()))

B=[]
for j in range(M):
    B.append(list(input()))

A=np.asarray(A)
B=np.asarray(B)
flg=False

  
for x in range(N-M):
    for y in range(N-M):
        if (A[x:x+M,y:y+M] == B).all():
            flg=True
if flg:
    print("Yes")
else:
    try:
        if (A == B).all():
            print("Yes")
        else:
            print("No")
    except:
        print("No")
n = int(input())
a = list(input().split())

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

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        d = b[i]
        break

p = []
for i in range(n):
    if a[i] == d:
        p.append(i)

w = p[0] + n - p[1]

c = [0 for _ in range(n + 2)]
d = [0 for _ in range(n + 2)]

L = 1
H = 1
for i in range(1, n + 2):
    L *= i
    H *= n + 2 - i
    c[i] = L
    d[i] = H

e = [0 for _ in range(w + 1)]
temp = 1
for i in range(1, w + 1):
    temp *= w + 1 - i
    e[i] = temp


def ncmb(k):
    return d[k] // c[k]

def wcmb(k):
    if k > w or k <= 0:
        return 0
    elif k == w:
        return 1
    else:
        return e[k] // c[k]

print(n)
for k in range(2, n + 2):
    ans = ncmb(k) - wcmb(k-1)
    print(ans % MOD)



### FIXED CODE ###

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

class ModInv:
    def __init__(self, size, MOD):
        self.inv = [0] * (size + 1)
        self.inv[1] = 1
        for i in range(2, size + 1):
            self.inv[i] = (-(MOD // i) * self.inv[MOD%i]) % MOD

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

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        break

first = a.index(b[i])
for i in range(first + 1, n + 1):
    if a[i] == a[first]:
        second = i

w = n + first - second

inv = ModInv(n + 1, MOD)
c = [1] * (n + 2)
d = [1] * (n + 2)

for i in range(n + 1):
    d[i + 1] = (d[i] * inv.inv[i + 1]) % MOD
for i in range(n + 1):
    c[i + 1] = (c[i] * (i + 1)) % MOD

print(n)
for k in range(2, n + 2):
    ans = (((c[n+1] * d[n+1-k]) % MOD) * d[k]) % MOD
    if w >= k - 1:
        ans -= (((c[w] * d[w-k+1]) % MOD) * d[k-1]) % MOD
    print( ans % MOD )
N, K = map(int, input().split())
h = [int(input()) for i in range(N)]

# 小さい順にソートする
#def sort(h):
#    if len(h) <= 1:
        return h
#    base = h[-1]
#    low_temp = [];
#    high_temp = [];
#    base_count = 1
#    for i in range(len(h)-1):
#        if h[i] < base:
#            low_temp.append(h[i])
#        elif h[i] > base:
#            high_temp.append(h[i])
#        else:
#            base_count += 1
#    low = sort(low_temp)
#    high = sort(high_temp)
#    return low + [base]*base_count + high

h.sort()
hantei = 10**10
for i in range(N-K+1):
    temp = h[i:i+K]
    temp_dif = max(temp) - min(temp)
    if temp_dif < hantei:
        hantei = temp_dif

print(hantei)


### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
print(min(h[i+K-1] - h[i] for i in range(N-K+1)))
while True:
  a,op,c = map(str, input().split())
  a = int(a)
  c = int(b)
  if op == '?': 
    break
  if op == '+':
    print(a+b)
  if op == '-':
    print(a-b)
  if op == '*':
    print(a*b)
  if op == '/':
    print(a//b)
  



### FIXED CODE ###

while True:
  a,op,b = map(str, input().split())
  a = int(a)
  b = int(b)
  if op == '?': 
    break
  if op == '+':
    print(a+b)
  if op == '-':
    print(a-b)
  if op == '*':
    print(a*b)
  if op == '/':
    print(a//b)
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
from collections import Counter as co
D=co(A)

cnt=0
for i in range(N):
  if D[A[-1-i]]>0:
    D[A[-1-i]]-=1
    for j in range(1,16):
      d=2**j
      if A[-1-i]<d:
        e=d-A[-1-i]
        break
    if D[e]>0:
      cnt+=1
      D[e]-=1
print(cnt)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
from collections import Counter as co
D=co(A)

cnt=0
for i in range(N):
  if D[A[-1-i]]>0:
    D[A[-1-i]]-=1
    d=A[-1-i]
    f=len(bin(d))-2
    e=2**f-d
    if D[e]>0:
      cnt+=1
      D[e]-=1
print(cnt)
N,K=map(int,input().split())
A=list(map(int,input().split()))
L=[]
B=set(A)
for i in B:
  x=A.count(i)
  L.append(x)
L.sort(reverse=True)
S=0
for i in range(K):
  S+=L[i]
print(N-S)

### FIXED CODE ###

from collections import Counter
N,K=map(int,input().split())
A=list(map(int,input().split()))
x=Counter(A)
l=x.most_common(K)
s=0
for i in range(len(l)):
  s+=l[i][1]
  
print(N-s)
def extgcd(a,b):
  r=[1,0,a]
  w=[0,1,b]
  while w[2]!=1:
    q=r[2]//w[2]
    r2=w
    w2=[r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
    r=r2
    w=w2
  return [w[0],w[1]]
def mod_inv(a,m):
  x=extgcd(a,m)[0]
  return (m+x%m)%m

def primes(n):
  is_prime=[True]*(n+1)
  is_prime[0]=False
  is_prime[1]=False
  for i in range(2,int(n**0.5)+1):
    if not is_prime[i]:
      continue
    for j in range(i*2,n+1,i):
      is_prime[j]=False
  return [i for i in range(n+1) if is_prime[i]]
def fact2(n):
  l=primes(int(n**0.5)+1)
  L=[]
  for i in range(len(l)):
    ct=0
    while n%l[i]==0:
      n=n//l[i]
      ct+=1
    L.append((l[i],ct))
    if n==1:
      break
  if n!=1:
    L.append(n)
  return L

n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(10**6)]
mod=10**9+7
for i in range(n):
  x=fact2(a[i])
  for j in range(len(x)):
    l[x[j][0]]=max(l[x[j][0]],x[j][1])
lcm=1
for i in range(2,10**6):
  lcm*=(i**l[i])
  lcm%=mod
ans=0
for i in range(n):
  ans+=lcm*mod_inv(a[i],mod)
  ans%=mod
print(ans)

### FIXED CODE ###

from fractions import gcd
import collections

def lcm(x, y):
  return (x*y)//gcd(x, y)
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(10**6)]
mod=10**9+7
for i in range(n):
  x=factorize(a[i])
  for j in range(len(x)):
    l[x[j][0]]=max(l[x[j][0]],x[j][1])
lcm=1
for i in range(2,10**6):
  lcm*=(i**l[i])
  lcm%=mod
ans=0
for i in range(n):
  ans+=lcm*mod_inv(a[i],mod)
  ans%=mod
print(ans)