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

def solve():
    MOD = 10**9 + 7

    N, K = map(int, input().split())
    Ass = [tuple(map(int, input().split())) for _ in range(N)]

    maxD = K.bit_length() - 1

    dp = [[[0]*(N) for j in range(N)] for i in range(maxD+1)]
    for v, As in enumerate(Ass):
        nums = [0] * N
        for v2, A in enumerate(As):
            if A == 1:
                nums[v2] += 1
        dp[0][v] = nums
    for d in range(1, maxD+1):
        for v in range(N):
            nums = [0] * N
            for v2, num2 in enumerate(dp[d-1][v]):
                for v3, num3 in enumerate(dp[d-1][v2]):
                    nums[v3] += num2 * num3
                    nums[v3] %= MOD
            dp[d][v] = nums

    anss = [1] * N
    for d in range(maxD+1):
        if K & (1<<d):
            ans2s = [0] * N
            for v in range(N):
                for v2, num in enumerate(dp[d][v]):
                    ans2s[v2] += anss[v] * num
                    ans2s[v2] %= MOD
            anss = ans2s

    print(sum(anss) % MOD)


solve()


### FIXED CODE ###

from collections import Counter

def solve():
    MOD = 10**9 + 7

    N, K = map(int, input().split())
    Ass = [tuple(map(int, input().split())) for _ in range(N)]

    maxD = K.bit_length() - 1

    dp = [[Counter() for _ in range(N)] for _ in range(maxD+1)]
    for v, As in enumerate(Ass):
        v2s = []
        for v2, A in enumerate(As):
            if A == 1:
                v2s.append(v2)
        dp[0][v] = Counter(v2s)
    for d in range(1, maxD+1):
        for v in range(N):
            for v2, num2 in dp[d-1][v].items():
                for v3, num3 in dp[d-1][v2].items():
                    dp[d][v][v3] += num2 * num3
                    dp[d][v][v3] %= MOD

    anss = [1] * N
    for d in range(maxD+1):
        if K & (1<<d):
            ans2s = [0] * N
            for v in range(N):
                for v2, num in dp[d][v].items():
                    ans2s[v2] += anss[v] * num
                    ans2s[v2] %= MOD
            anss = ans2s

    print(sum(anss) % MOD)


solve()
### BUGGY CODE ###


def main():
    N = int(input())
    a_list = get_a_list()

    a_list.sort(reverse=True)

    sum_second_a = 0
    
    while len(a_list) > 0:
        a_list.pop(0)
        sum_second_a += a_list.pop(0)
        a_list.pop(-1)

    print(sum_second_a)

def get_a_list():
    a_list = []
    strs = input().split()

    for a in strs:
        a_list.append(int(a))

    return a_list


if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    N = int(input())
    a_list = get_a_list()

    a_list.sort(reverse=True)

    sum_second_a = 0
    
    a_list = a_list[:2*N]
    for i in range(1, 2*N, 2):
        sum_second_a += a_list[i]

    print(sum_second_a)

def get_a_list():
    a_list = []
    strs = input().split()

    for a in strs:
        a_list.append(int(a))

    return a_list


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

# 2020/07/26
# diverta 2019 Programming Contest - B

# Input
r, g, b, n = map(int,input().split())

ans = 0

# Calc
for ir in range(n+1):
    vr = r * ir 
    if vr > n:
        break

    for ig in range(n+1):
        vg = g * ig 
        if vg > n:
            break
        cb = n - vr - vg
        if cb >= 0 and cb % b == 0:
            ans = ans + 1

# Output
print(ans)


### FIXED CODE ###

# 2019/05/12
# diverta 2019 Programming Contest - B

# Input
r, g, b, n = map(int, input().split())

# Init
cnt = 0

# Calc
for i in range(n+1):
    rcnt = r * i
    if rcnt > n:
        break
    
    for j in range(n+1):
        rgcnt = rcnt + g * j
        if rgcnt > n:
            break
        bcnt = n - rgcnt
        if bcnt % b == 0:
            cnt += 1
# Output
print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
l = [None] * M
for i in range(M):
	p, y = map(int, input().split())
	l[i] = [y, p, i]
m = []
for i in range(1, N + 1):
	l_ = sorted(list(filter(lambda x: x[1] == i, l)))
	for i in range(len(l_)):
		l_[i][0] = i + 1
	m = m + l_
for i in sorted(m, key = lambda x: x[2]):
	p = str(i[1])
	y = str(i[0])
	print('0' * (6 - len(p)) + p + '0' * (6 - len(y)) + y)

### FIXED CODE ###

N, M = map(int, input().split())
l = [None] * M
for i in range(M):
	p, y = map(int, input().split())
	l[i] = [p, y, i]
l.sort()
ans = []
t = l[0][0]
x = 0
for i in l:
	if t == i[0]:
		x += 1
		ans.append([i[2], i[0], x])
	else:
		t = i[0]
		x = 1
		ans.append([i[2], i[0], x])
ans.sort()
for i in ans:
	p = str(i[1])
	x = str(i[2])
	print('0' * (6 - len(p)) + p + '0' * (6 - len(x)) + x)
### BUGGY CODE ###

#from fractions import gcd
from collections import Counter
mod = 10**9+7
def inv(a):
  return pow(a,mod-2,mod)
def prm(a):
  if a == 1 or a == 4:
    return False
  for i in range(2,int((a)**0.5+1)):
    if a%i == 0:
      return False
  else:
    return True
prime = []
for i in range(1,10**4+1):
  if prm(i):
    prime.append(i)
def sepa(a):
  ans = []
  while a>1:
    for x in prime:
      if a%x == 0:
        ans.append(x)
        a = a//x
        break
  return Counter(ans)
n = int(input())
a = list(map(int,input().split()))
f = [inv(a[i]) for i in range(n)]
lcm = sepa(1)
for i in range(n):
  x = sepa(a[i])
  for y,z in x.items():
    if z>lcm[y]:
      lcm[y] = z
k = 1
for i,j in lcm.items():
  k = k*(i**j)%mod
print(k*sum(f)%mod)

### FIXED CODE ###

#from fractions import gcd
from collections import Counter
mod = 10**9+7
def inv(a):
  return pow(a,mod-2,mod)
def prm(a):
  if a == 1 or a == 4:
    return False
  for i in range(2,int((a)**0.5+1)):
    if a%i == 0:
      return False
  else:
    return True
prime = []
for i in range(1,10**4+1):
  if prm(i):
    prime.append(i)
def sepa(a):
  ans = []
  while a>1:
    for x in prime:
      if a%x == 0:
        ans.append(x)
        a = a//x
        break
      elif x == prime[-1]:
        ans.append(a)
        a = 1
  return Counter(ans)
n = int(input())
a = list(map(int,input().split()))
f = [inv(a[i]) for i in range(n)]
lcm = sepa(1)
for i in range(n):
  x = sepa(a[i])
  for y,z in x.items():
    if z>lcm[y]:
      lcm[y] = z
k = 1
for i,j in lcm.items():
  k = k*(i**j)%mod
print(k*sum(f)%mod)
### BUGGY CODE ###

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

def gcd_l(A):
    if len(A) == 1:
        return A[0]
    x = gcd(A[0], A[1])
    if len(A) == 2:
        return x
    for i in range(2, len(A)):
        x = gcd(x, A[i])
    return x

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

ans = 1
for i in range(N):
    B = A[:i] + A[i+1:]
    ans = max(ans, gcd_l(B))

print(ans)


### FIXED CODE ###

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

def gcd_l(A):
    if len(A) == 1:
        return A[0]
    x = gcd(A[0], A[1])
    if len(A) == 2:
        return x
    for i in range(2, len(A)):
        x = gcd(x, A[i])
    return x

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

B = []
C = []
x = A[0]
y = A[-1]
for i in range(N):
    x = gcd(x, A[i])
    B.append(x)
    y = gcd(y, A[N-1-i])
    C.append(y)
    
ans = 1

for i in range(1, N-1):
    ans = max(ans, gcd(B[i-1], C[N-2-i]))

ans = max(ans, B[N-2], C[N-2])

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

N, P = map(int, input().split())
S = list(input())
mod = P
dp = [[0 for i in range(N-j)] for j in range(N)]
dp
for j in range(N):
    dp[j][0]=(int(S[j])%mod)
    for i in range(1,N-j):
        dp[j][i]=((dp[j][i-1]*10+int(S[j+i]))%mod)
ans = 0
for i in range(N):
    ans += dp[i].count(0)
    
print(ans)


### FIXED CODE ###

from collections import Counter

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

def solve_2(S):
    ind = (i for i, x in enumerate(S, 1) if x % 2 == 0)
    return sum(ind)

def solve_5(S):
    ind = (i for i, x in enumerate(S, 1) if x % 5 == 0)
    return sum(ind)

def solve(S,P):
    if P == 2:
        return solve_2(S)
    if P == 5:
        return solve_5(S)
    S = S[::-1]
    T = [0] * len(S)
    T[0] = S[0] % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * S[i]
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]


print(solve(S,P))
### BUGGY CODE ###

from bisect import bisect_left

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

d = {}

for py in PY:
    d[py[0]] = d.get(py[0],[])+[py[1]]

for k in d:
    d[k].sort()

for py in PY:
    s1 = str(py[0])
    s1 = ("0"*(6-len(s1)))+s1
    s2 = str(bisect_left(d[py[0]],py[1])+1)
    s2 = ("0"*(6-len(s2)))+s2

    print(s1+s2)


### FIXED CODE ###

N,M = map(int,input().split())
PY = [list(map(int,input().split()))+[i] for i in range(M)]

num = [0]*N
ans = [""]*M

PY.sort(key = lambda x:x[1])

for p,y,i in PY:
    num[p-1] += 1
    ans[i] = str(p).zfill(6) + str(num[p-1]).zfill(6)

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

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

mod = 10 ** 9 + 7
ans = sum((A[i] % mod) * (A[j] % mod) for i in range(0,N-1) for j in range(i+1,N))

print(ans % mod)

### FIXED CODE ###

mod = 1000000007
N = int(input())
A = list(map(lambda x: int(x) % mod, input().split(" ")))

"""
累積話を計算しておく: O(N)
"""
_sum = 0
for i in range(N):
    _sum += A[i]
    _sum %= mod

"""
1重ループ内で下記を行う: O(N)

- 端のブロックを累積和から崩す（減算）
- 端のブロックと累積和をかける
- modをとる
"""
ans = 0
for i in range(N):
    # 累積和の端のブロックを崩す
    _sum -= A[i]

    ans += A[i] * _sum
    ans %= mod

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

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,m = MAP()
a = [INT() for _ in range(m)]

def fib(n):
    if (n==1) or (n==2):
        return 1
    else:
        return fib(n-1)+fib(n-2)

start = 0
ans = 1

for k in a:
    tmp = k-start
    if tmp==0:
        print(0)
        exit(0)
    ans *= fib(tmp)
    ans%=MOD
    start = k+1

ans*=fib(n-start+1)
ans%=MOD

print(ans)

### FIXED CODE ###

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,m = MAP()
a = [INT() for _ in range(m)]

# 高速版
def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]

start = 0
ans = 1

for k in a:
    tmp = k-start
    if tmp==0:
        print(0)
        exit(0)
    ans *= fib(tmp)
    ans%=MOD
    start = k+1

ans*=fib(n-start+1)
ans%=MOD

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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

s = STR()
arr = [-1 for _ in range(len(s))]
for i in range(len(s)):
    arr[i] = int(s[i:]) % 2019
a = list(set(arr))
b = Counter(arr)
ans = 0
for i in a:
    if i == 0:
        ans += (b[i] + 1) * b[i] // 2
    else:
        ans += b[i] * (b[i] - 1) // 2
print(ans)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

s = [int(i) for i in STR()]
l = len(s)
arr = [-1 for _ in range(l)]
tmp = 0
for i in range(l):
    tmp += s[i] * pow(10, l - i, 2019)
    tmp %= 2019
    arr[i] = tmp
arr.sort()
tmp = arr[0]
cnt = 1
ans = 0
for i in range(1, l):
    if tmp == arr[i]:
        cnt += 1
    else:
        ans += cnt * (cnt - 1) // 2
        if tmp == 0:
            ans += cnt
        cnt = 1
        tmp = arr[i]
ans += cnt * (cnt - 1) // 2
if tmp == 0:
    ans += cnt
print(ans)
### BUGGY CODE ###

import numpy as np
N=int(input())
a=np.array(list(map(int,input().split())))
a0 = a[0]
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
ma = N
mi = N//2
for i in range(len(bin(N))-2):
    for j in range(ma,mi,-1):
        if a[j-1]==1:
            tg_list = make_divisors(j)
            for k in tg_list:
                if k!=j:
                    a[k-1] += 1
    a %= 2
    #print(a)
    ma = mi
    mi = mi//2
if sum(a)%2 == a0:
    #print(a)
    res = [str(i+1) for i in range(N) if a[i]==1]
    print(len(res))
    if len(res)!=0:
        print(' '.join(res))
else:
    print(-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N=int(input())
a=list(map(int,input().split()))
a0 = a[0]
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
ma = N
mi = N//2
for i in range(len(bin(N))-2):
    for j in range(ma,mi,-1):
        if a[j-1]%2==1:
            tg_list = make_divisors(j)
            for k in tg_list:
                if k!=j:
                    a[k-1] += 1
    #a[mi//2:mi] %= 2
    #print(a)
    ma = mi
    mi = mi//2
if sum(a)%2 == a0:
    #print(a)
    res = [str(i+1) for i in range(N) if a[i]%2==1]
    M = len(res)
    print(M)
    if M!=0:
        print(' '.join(res))
else:
    print(-1)
### BUGGY CODE ###

S = input()
Q = int(input())

rev = False

for i in range(Q):
    # クエリを受け取る
    query = input().split()
    # 反転の操作
    if query[0] == '1':
        if rev == True:
            rev = False
        else:
            rev = True
    else:
        # 追加する操作
        F = int(query[1])
        C = query[2]
        # 先頭に追加する場合
        if F == 1:
            # 反転しているとき
            if rev == True:
                # 末尾に追加
                S = S + C
            # 反転していないとき
            else:
                # 先頭に追加
                S = C + S
        # 末尾に追加する場合
        else:
            # 反転しているとき
            if rev == True:
                # 先頭に追加
                S = C + S
            # 反転していないとき
            else:
                # 末尾に追加
                S = S + C
if rev == True:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

S = input()
Q = int(input())
Query = [input().split() for _ in range(Q)]

rev = False
S1 = ''
S2 = ''

for TFC in Query:
    if TFC[0] == '1':
        rev = not rev
    else:
        if TFC[1] == '1':
            if rev:
                S2 += TFC[2]
            else:
                S1 = TFC[2] + S1
        else:
            if rev:
                S1 = TFC[2] + S1
            else:
                S2 += TFC[2]

if rev:
    print(S2[::-1] + S[::-1] + S1[::-1])
else:
    print(S1 + S + S2)
### BUGGY CODE ###

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

n = int(input())

a = []

for i in range(n):
    a.append(int(input()))

a_max = max(a)

for i in range(0,n):
    if a[i] == a_max:
        a1 = a[:i]
        a2 = a[i+1:]

        if len(a1) == 0:
                print(max(a2))
        elif len(a2) == 0:
            print(max(a1)) 
        else:
            print(max(max(a1), max(a2)))
    else:
        print(a_max)

    


### FIXED CODE ###

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

n = int(input())

a = []

for i in range(n):
    a.append((i, int(input())))

a_sorted = sorted(a, key = lambda k:k[1])
max_index = a_sorted[-1][0]

#print(a_sorted)

a_max = a_sorted[-1][1]
a_sec_max = a_sorted[-2][1]

for i in range(0,n):
    if i != max_index:
        print(a_max)
    else:
        print(a_sec_max)
### BUGGY CODE ###

N = int(input())
S = list(input())

ans = float('inf')
for i in range(len(S)):
    cnt = 0
    Right = S[i+1:]
    Left = S[:i]
    cnt += Right.count('E')  #右にいて東を向いている人の数
    cnt += Left.count('W')  #左にいて西を向いている人の数
    if cnt >= ans:
        continue
    
    ans = cnt

print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())

cnt_right = S[1:].count('E')
cnt_left = 0
ans = cnt_right + cnt_left

for ichi in range(len(S)-1):
    if S[ichi] == 'W':
        cnt_left += 1
    if S[ichi+1] == 'E':
        cnt_right -= 1
    ans = min(ans, cnt_right + cnt_left)
    
print(ans)
### BUGGY CODE ###

from fractions import gcd

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

x = 1
for i in range(N):
  x = (x*A[i]) // gcd(x, A[i])

ans = 0
for a in A:
  ans += x//a
  ans %= mod
print(ans)


### FIXED CODE ###

from fractions import gcd

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

x = 1
for i in range(N):
  x = (x*A[i]) // gcd(x, A[i])

ans = 0
for a in A:
  ans += x//a
  #ans %= mod
print(ans%mod)
### BUGGY CODE ###

n,m=map(int,input().split())
h = list(map(int, input().split()))
good = []
bad = []
ans =[]

for i in range(m):
    a,b=map(int,input().split())
    if h[a-1] > h[b-1]:
        good.append(a)
        bad.append(b)
    elif h[a-1] == h[b-1]:
        bad.append(a)
        bad.append(b)
    else:
        good.append(b)
        bad.append(a)

j = 1
for j in range(n+1):
    if j in bad:
        pass
    else:
        ans.append(j)
    j += 1
        

print(len(ans)-1)

### FIXED CODE ###

n,m=map(int,input().split())
h = list(map(int, input().split()))
bad = []

for i in range(m):
    a,b=map(int,input().split())
    if h[a-1] > h[b-1]:
        bad.append(b)
    elif h[a-1] == h[b-1]:
        bad.append(a)
        bad.append(b)
    else:
        bad.append(a)

bad_two = set(bad)
ans = n - len(bad_two)
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
for i in range(int(M/N)):
    if M%(int(M/N)-i)==0:
        ans=int(M/N)-i
        print(ans)
        break


### FIXED CODE ###

N,M=map(int,input().split())
ans=0
for i in range(1,10**5):
    if M%i==0:
        a=max(M//i,i)
        b=min(M//i,i)
        if M//a>=N and ans<a:
            ans=a
        if M//b>=N and ans<b:
            ans=b
print(ans)
### BUGGY CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
def lcm(l,r):
    g=gcd(l,r)
    res=(l//g)*(r//g)*g
    return res
l=1
r=10**6
res=a[0]
for i in a:
    res=lcm(res,i)
ans=0
for i in a:
    ans+=(res//i)%mod
print(ans%mod)

### FIXED CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
a=list(map(int,input().split()))

Mod=10**9+7
M=10**6+2 #書き換え
fac=[0]*M
finv=[0]*M
inv=[0]*M

#finvに逆元、facに階乗のmod
def COMinit():
  fac[0]=fac[1]=1
  finv[0]=finv[1]=1
  inv[1]=1
  for i in range(2,M):
    fac[i]=(fac[i-1]*i%Mod)%Mod
    inv[i]=Mod-inv[Mod%i]*(Mod//i) %Mod
    finv[i]=(finv[i-1]*inv[i]%Mod)%Mod
def COM(n,k):
  if n<k:
    return 0
  if n<0 or k<0:
    return 0
  return (fac[n]*(finv[k]*finv[n-k]%Mod)%Mod)%Mod

COMinit()

def factorize(n):
    fct={}
    temp=n
    if temp<4:
        fct[temp]=1
    else:
        e=0
        while temp%2==0:
            temp=temp//2
            e+=1
        if e>0:
            fct[2]=e
    
    for b in range(3,int(n**0.5)+1,2):
        e=0
        while temp%b == 0:
            temp=temp//b
            e+=1
        if e>0:
            fct[b]=e
    if temp!=1:
        fct[temp]=1
    return fct

res={}
for i in a:
    f=factorize(i)
    for j in f:
        if j not in res:
            res[j]=f[j]
        else:
            res[j]=max(res[j],f[j])
c=1
ans=0
for i in res:
    c*=pow(i,res[i],Mod)
    c%=Mod
for i in a:
    ans+=c*inv[i]
    ans%=Mod
print(ans)
### BUGGY CODE ###

n=int(input())
l=input().split()
li=[int(i) for i in l]
for m in range(1,n+1):
    print(li.count(m))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
for i in a:
    ans[i-1]+=1
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

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

score = 0
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    for k in range(j + 1, n):
      a = l_list[i]
      b = l_list[j]
      c = l_list[k]
      if (a + b > c) and (b + c > a) and (c + a > b):
        score += 1
        
print(score)

### FIXED CODE ###

import bisect

n = int(input())
l_list = list(map(int, input().split()))
l_list.sort()

score = 0
#a_before = 0
#b_before = 0
for i in range(0, n - 2):
  a = l_list[i]
  #if a_before == a:
  #  continue
  #a_before = a
  
  for j in range(i + 1, n - 1):
    b = l_list[j]
    #if b_before == b:
    #  continue
    #b_before = b
    
    #minimum = b - a
    maximum = a + b
    
    #idx_minimum = bisect.bisect_right(l_list, minimum)
    idx_maximum = bisect.bisect_left(l_list, maximum)
    
    score += max(0, idx_maximum - j - 1)
        
print(score)
### BUGGY CODE ###

import sys
# x,y = map(int,input().split())
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
ans = 0
M = 1000005
cnt = [0 for _ in range(M)]

for x in a:
    for j in range(x,M,x):
        cnt[j] += 1
    
for x in a:
    if cnt[x] == 1:
        ans += 1


print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
ans = 0
M = 1000005
cnt = [0 for _ in range(M)]
mx = max(a)+1
for x in a:
    for j in range(x,mx,x):
        cnt[j] += 1
    
for x in a:
    if cnt[x] == 1:
        ans += 1


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

n = int(input())

a = [int(input()) for i in range(n)]
ma = max(a)

for i in range(n):
    if a[i] == ma:
        a[i] = 1
        print(max(a))
        a[i] = ma
    else:
        print(ma)

### FIXED CODE ###

n = int(input())

a = [int(input()) for i in range(n)]
ma1 = max(a)
ma2 = a.count(ma1)

for i in range(n):
    if a[i] == ma1:
        if ma2 == 1:
            a[i] = 1
            print(max(a))
            a[i] = ma1
        else:
            print(ma1)
    else:
        print(ma1)