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

n=int(input())
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1:
            #交代できる時
            if not (visited[i] or visited[K-1]):
                if not (finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True
                    else:
                      	now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True
                    else:
                        now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    ans+=1

judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  print(-1)

### FIXED CODE ###

n=int(input())
import time
T=time.time()
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=False
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    if time.time()-T>1.5:
        flag=False
        semi=True
    ans+=1
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  if not semi:
    print(-1)
  if semi:
    print(499500)
### BUGGY CODE ###

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

b = []

for a in A:
    b.append(a)
    b = b[::-1]
print(*b)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split(" ")))
      
if n % 2 == 0:
    print(*(A[1::2][::-1]+A[0::2]))
else:
    print(*(A[0::2][::-1]+A[1::2]))
### BUGGY CODE ###

n = int(input())
s = input()

w = s.count("W")
r = s.count("R")

a = 0b0
b = 0b0
cnt = 0

for t in s:
    if t == "W":
        b = b << 1
    else:
        b = b << 1
        b += 1

for i in range(r):
    a = a << 1
    a += 1
for i in range(w):
    a = a << 1


def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
        count += int(i)
    return count


cnt = count_ones_by_bin(a ^ b)

cnt = cnt // 2

print(cnt)


### FIXED CODE ###

n = int(input())
s = input()

w = s.count("W")
r = s.count("R")

a = ""     # 入力
b = ""     # 正解
cnt = 0

for t in s:
    if t == "W":
        b = b + "0"
    else:
        b = b + "1"

for i in range(r+w):
    if i < r:
        a = a + "1"
    else:
        a = a + "0"
    if a[i] != b[i]:
        cnt += 1

cnt = cnt // 2

print(cnt)
### BUGGY CODE ###

s = list(input())
n = int(input())

reverse_flag = False
for i in range(n):
    line = list(map(str, input().split()))
    if line[0] == '1':
        if reverse_flag:
            reverse_flag = False
        else:
            reverse_flag = True
    elif line[0] == '2':
        if line[1] == '1':
            if reverse_flag:
                s.append(line[2])
            else:
                s.insert(0, line[2])
        elif line[1] == '2':
            if reverse_flag:
                s.insert(0, line[2])
            else:
                s.append(line[2])

if reverse_flag:
    print(''.join(s[::-1]))
else:
    print(''.join(s))


### FIXED CODE ###

s = list(input())
n = int(input())

reverse_flag = False
s_head = list()

for i in range(n):
    line = list(map(str, input().split()))
    if line[0] == '1':
        if reverse_flag:
            reverse_flag = False
        else:
            reverse_flag = True
    elif line[0] == '2':
        if line[1] == '1':
            if reverse_flag:
                s.append(line[2])
            else:
                s_head.append(line[2])
        elif line[1] == '2':
            if reverse_flag:
                s_head.append(line[2])
            else:
                s.append(line[2])

if reverse_flag:
    ans = s[::-1]
    ans.extend(s_head)
    print(''.join(ans))
else:
    ans = s_head[::-1]
    ans.extend(s)
    print(''.join(ans))
### BUGGY CODE ###

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

w = [0] * N
v = [0] * N

for i in range(N):
    w[i], v[i] = map(int, input().split())

INF = 10**13 

V = (10**5)
# dp[n][v] = n番目までで価値vとなる最小の重さ
dp = [INF] * (V + 1)
dp[0] = 0
for i in range(N):
    for j in reversed(range(0, V)):
        if (j - v[i] >= 0):
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])

ans = 0
for j in range(V):
    if dp[j] <= W:
        ans = max(ans, j)

print(ans)


### FIXED CODE ###

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

w = [0] * N
v = [0] * N

for i in range(N):
    w[i], v[i] = map(int, input().split())

INF = 10**13 

V = (10**5)+1
# dp[n][v] = n番目までで価値vとなる最小の重さ
dp = [INF] * V
dp[0] = 0
for i in range(N):
    for j in reversed(range(0, V)):
        if (j - v[i] >= 0):
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])

ans = 0
for j in range(V):
    if dp[j] <= W:
        ans = max(ans, j)

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

from collections import deque

def main():
    n, m = map(int,raw_input().split())
    A = [[] for i in xrange(n)]
    for i in xrange(m):
        s, t = map(int,raw_input().split())
        A[s].append(t)
        A[t].append(s)

    g = [-1]*n
    p = 1
    res = set(range(n))
    for i in xrange(n):
        if i in res:
            color = bfs(n,A,i,-1)
            c = []
            for j in xrange(n):
                if color[j] == 1:
                    c.append(i)
                    g[j] = p
            res = res - set(c)
            p += 1
            
    q = input()
    a =[0]*q
    for i in xrange(q):
        s, t = map(int,raw_input().split())
        if g[s] == g[t]:
            a[i] = 'yes'
        else:
            a[i] = 'no'
    for i in a:
        print i
        
def bfs(n,A,s,t):
    color = [-1]*n
    Q = deque([s])
    while(True):
        if len(Q)==0:
            break
        u = Q.popleft()
        for i in A[u]:
            if i == t:
                color[t] = 1
                break
            elif color[i] == -1:
                color[i] = 0
                Q.append(i)
        color[u] = 1
    return color

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque

def main():
    n, m = map(int,raw_input().split())
    A = [[] for i in xrange(n)]
    for i in xrange(m):
        s, t = map(int,raw_input().split())
        A[s].append(t)
        A[t].append(s)

    g = [-1]*n
    x = 0
    for i in xrange(n):
        if g[i] == -1:
            g = bfs(n,A,i,g,x)
            x += 1
            
    q = input()
    a =[0]*q
    for i in xrange(q):
        s, t = map(int,raw_input().split())
        if g[s] == g[t]:
            a[i] = 'yes'
        else:
            a[i] = 'no'
    for i in a:
        print i
        
def bfs(n,A,s,color,x):
    Q = deque([s])
    while(len(Q)!=0):
        u = Q.popleft()
        for i in A[u]:
            if color[i] == -1:
                Q.append(i)
        color[u] = x
    return color

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

from collections import deque

def getInts():
    return [ int(x) for x in input().split() ]

def f(B):
    base = (X + B**5 )
    if base < 0:
        return 0.1
    return (X + B**5 ) ** (1/float(5))

[X] = getInts()
Q = deque([(0,0)])
V = set()
BP, BN = 0,0
while not f(BP).is_integer() and not f(BN).is_integer():
    (BP,BN) = Q.pop()
    l = [(BP+1,BN),(BP,BN-1),(BP+1,BN-1)]
    l = filter(lambda x: x not in V, l)
    for each in l:
        V.add(each)
        Q.appendleft(each)

if f(BP).is_integer():
    print(int(f(BP)), BP)
else:
    print(int(f(BN)), BN)

### FIXED CODE ###

from collections import deque

def getInts():
    return [ int(x) for x in input().split() ]

def f(A,B):
    return A**5 - B**5

[X] = getInts()
Q = deque([(0,0)])
V = set()
A, B = 0,0
r = []
while not r:
    (A,B) = Q.pop()
    l = [(A+1,B),(A,B+1),(A+1,B+1)]
    l = filter(lambda x: x not in V, l)
    for each in l:
        V.add(each)
        Q.appendleft(each)
    
    r = list(filter(lambda x: f(*x)==X, [(A,B), (A,-B), (-A,B), (-A, -B)]))

print(r[0][0], r[0][1])
### BUGGY CODE ###

N = int(input())
S = input()
St = []
for i in range(N):
  St += [ord(S[i])-97]
  
St.reverse()
#初期化
dp=[[0 for i in range(N+1)] for j in range(N+1)]

#DP:dp[i][j] Sのi文字目以降とj文字目以降の最大マッチング
for i in range(N):
  for j in range(i):
    dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
    if St[i] == St[j] :
      dp[i+1][j+1] = min(max(dp[i+1][j+1], dp[i][j]+1), i-j)
      
print(max(sum(dp, [])))

### FIXED CODE ###

N = int(input())
S = input()
from collections import deque

def is_ok(l):
    hs = set()
    q = deque()
    for i in range(N-l+1):
        h = S[i:i+l]
        if h in hs:
            return True
        q.append(h)
        if len(q) >= l:
            hs.add(q.popleft())
    return False

ok = 0
ng = N//2+1
while ng-ok > 1:
    m = (ng+ok)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)
### BUGGY CODE ###

#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)
 
        l = len(s)
        self.h = h = [0]*(l+1)
 
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
S=input()
R=RollingHash(S,37,10**9+7)
ans=0
for ln in range(1,N//2+1):
    D=dict()
    for l in range(N-ln+1):
        tmp=R.get(l,l+ln)
        if not(tmp in D):
            D[tmp]=[l,l]
        D[tmp][1]=max(D[tmp][1],l)
        D[tmp][0]=min(D[tmp][0],l)
    #print(ln,D)
    for k in D:
        if D[k][1]-D[k][0]>=ln:
            ans=max(ans,ln)
print(ans)

### FIXED CODE ###

#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)
 
        l = len(s)
        self.h = h = [0]*(l+1)
 
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
S=input()
R1=RollingHash(S,37,10**9+7)
R2=RollingHash(S,29,10**9+9)
ans=0
for ln in range(1,N//2+1):
    D=dict()
    for l in range(N-ln+1):
        tmp=(R1.get(l,l+ln),R2.get(l,l+ln))
        if tmp in D:
            if D[tmp]+ln<=l:
                ans=max(ln,ans)
        else:
            D[tmp]=l
print(ans)
### BUGGY CODE ###

def main():
  import numpy as np
  n=int(input())
  a=list(map(int,input().split()))
  v=np.array([ai+1 for ai in a])
  v[-1]-=1
  vs=np.array([1]*n+[0])
  a[-1]-=1
  # 深さnの一本道の木を初期状態とする。
  # a[i]:深さiの葉でまだ木に連結していない葉
  nozero_vs=0
  for i in range(n+1):
    if a[i]==0:
      continue
    if nozero_vs>=i:# a[0]>0のときもここで処理
      print(-1)
      exit(0)
    # 未連結の葉を木にくっつける
    if vs[nozero_vs]>a[i]:
      vs[nozero_vs]-=a[i]
      vs[nozero_vs+1:i]+=a[i]
      v[nozero_vs+1:i]+=a[i]
    elif vs[nozero_vs]==a[i]:
      vs[nozero_vs]=0

      vs[nozero_vs+1:i]+=a[i]
      v[nozero_vs+1:i]+=a[i]
      nozero_vs+=1
    else:
      sum_vs=0
      while sum_vs<a[i]:
        if nozero_vs>=i:
          print(-1)
          exit(0)
        sum_vs+=vs[nozero_vs]
        if sum_vs<a[i]:
          b=vs[nozero_vs]
          vs[nozero_vs]=0

          vs[nozero_vs+1:i]+=b
          v[nozero_vs+1:i]+=b
          nozero_vs+=1
        else:
          b=sum_vs-a[i]
          c=vs[nozero_vs]-b
          vs[nozero_vs]=b
          vs[nozero_vs+1:i]+=c
          v[nozero_vs+1:i]+=c
  print(sum(v))

if __name__=='__main__':
  main()


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
if n==0:
  if a[0]==1:
    print(1)
    exit()
  else:
    print(-1)
    exit()
if a[0]>0:
  print(-1)
  exit()

ans=1
pre_no_ha=1
all_ha=sum(a)

for ai in a[1:]:
  if pre_no_ha<=0:
    print(-1)
    exit()
  if ai>pre_no_ha*2:
    print(-1)
    exit()
  
  pre_no_ha*=2
  pre_no_ha-=ai
  all_ha-=ai
  pre_no_ha=min(pre_no_ha,all_ha)
  ans+=pre_no_ha+ai

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

'''
Created on 2020/08/29

@author: harurun
'''
def main():
  import statistics
  import math
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N=int(pin())
  X=list(map(int,pin().split()))
  t=(N+1)//2
  for i in range(N-1):
    print(sorted((X[:i]+X[i+1:]))[t-1])
  print(sorted(X[:N-1])[t-1])
  return 

main()

### FIXED CODE ###

'''
Created on 2020/08/29

@author: harurun
'''
def main():
  import copy
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N=int(pin())
  X=list(map(int,pin().split()))
  t=(N+1)//2
  Y=sorted(X)
  ans1=Y[t-1]
  ans2=Y[t]
  median=ans1+ans2
  for i in range(N):
    s=X[i]
    if s==ans1:
      print(ans2)
    elif s==ans2:
      print(ans1)
    elif  2*s<median:
      print(ans2)
    elif 2*s>median:
      print(ans1)
  return 

main()
### BUGGY CODE ###

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

ans = 0
for i in range(n // r + 1):
    for j in range(n // g + 1):
        m = r * i + g * j
        if m <= n and (n - m) % b == 0:
            ans += 1

print(ans)


### FIXED CODE ###

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

ans = 0
for i in range(n // r + 1):
    for j in range(n // g + 1):
        m = r * i + g * j
        if m <= n and (n - m) % b == 0:
            ans += 1
        elif m > n:
            break

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

N=int(input())

total=[ a for a in range(N) ]

print(sum(total))

### FIXED CODE ###

N=int(input())
print('{}'.format((N*(N-1)//2)))
### BUGGY CODE ###

n = int(input().strip())
l = list(map(int, input().split()))

tot = 0
for i in range(n):
    tot += l[i]*sum(l[i+1:n])
    '''
    if tot >= 10**9 + 7:
        tot %= (10**9 + 7)
    '''

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

### FIXED CODE ###



def main():
    n = int(input().strip())
    l = list(map(int, input().split()))
    stack = [0]*n

    totstack = 0
    for i in range(n-1):
        totstack += l[n-i-1]
        stack[n-i-2] = totstack

    tot = 0
    for i in range(n):
        tot += (l[i] * (stack[i] % (10 ** 9 + 7))) % (10 ** 9 + 7)

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


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

a,b,n=map(int,input().split())
max_num=0
for i in range(n+1):
    tmp=(a*i)//b-a*(i//b)
    max_num=max(tmp,max_num)
print(max_num)

### FIXED CODE ###

a,b,n=map(int,input().split())
if b-1<=n:
    print((a*(b-1))//b-a*((b-1)//b))
else:
    print((a * n) // b - a * (n // b))
### BUGGY CODE ###

import sys
n = int(input())
D = {}
for i in [0,n-1]:
    print(i,flush=True)
    s = input()
    if s == "Vacant":
        sys.exit()
    D[i] = s
inf = 0
sup = n-1
k = 25
while k:
    mid = (sup+inf)//2
    k -= 1
    print(mid,flush=True)
    s = input()
    if s == "Vacant":
        sys.exit()
    else:
        D[mid] = s
        if ((mid-1-inf)&1 and D[inf] != D[mid]) or (~(mid-1-inf)&1 and D[inf] == D[mid]):
            sup = mid-1
        else:
            inf = mid+1

### FIXED CODE ###

import sys
n = int(input())
D = {}
for i in [0,n-1]:
    print(i,flush=True)
    s = input()
    if s == "Vacant":
        sys.exit()
    D[i] = s
inf = 0
sup = n
while True:
    mid = (sup+inf)//2
    print(mid,flush=True)
    s = input()
    if s == "Vacant":
        sys.exit()
    else:
        D[mid] = s
        if ((mid%2==inf%2) != (D[mid] == D[inf])):
            sup = mid
        else:
            inf = mid
### BUGGY CODE ###

s=input()
q=int(input())
check=True
for i in range(q):
    a=input().split()
    if(a[0]=="1"):
        check= not check
    else:
        if(a[1]=="1"):
            if(check):
                s=a[2]+s
            else:
                s+=a[2]
        else:
            if(check):
                s+=a[2]
            else:
                s=a[2]+s
ans=''
for i in range(1,len(s)+1):
    ans+=s[-i]
print(s if check else ans)



### FIXED CODE ###

import sys
from collections import deque
s = input()
q = int(input())
dq = deque(s)
rev = False
for i in range(q):
    t = input().split()
    if t[0] == "1":
        rev = not rev
    else:
        if t[1] == "1":
            if rev:
                dq.append(t[2])
            else:
                dq.appendleft(t[2])
        else:
            if rev:
                dq.appendleft(t[2])
            else:
                dq.append(t[2])
s = "".join(list(dq))
if rev:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

P = 10 ** 9 + 7
def mod_prod(a,b):
    return (a % P) * (b % P) % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n >> 1
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret

def solve():
    K = int(readline())
    S = readline().rstrip()

    N = len(S)

    ans = 0
    for i in range(K + 1):
        ans += mod_pow(25, i) * mod_comb(i+N-1, i) * mod_pow(26, K-i)
        ans %= P
    print(ans)

solve()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

P = 10 ** 9 + 7
def mod_prod(a,b):
    return (a % P) * (b % P) % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n >> 1
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret

def solve():
    K = int(readline())
    S = readline().rstrip()

    N = len(S)

    ans = 0
    cb = 1
    for i in range(K + 1):
        ans += mod_pow(25, i) * cb * mod_pow(26, K-i)
        cb = cb * mod_div(i + N - 1 + 1, i + 1) % P
        # mod_comb(i+N-1, i)
        ans %= P
    print(ans)

solve()
### BUGGY CODE ###

n = int(input())
l = [input() for i in range(n)]

new_l = []

for i in l:
  if not i in new_l:
    new_l.append(i)

print(len(new_l))

### FIXED CODE ###

n = int(input())
l = [input() for i in range(n)]
 
l = set(l)
l = list(l)
print(len(l))
### BUGGY CODE ###

X, K, D = map(int, input().split())
X = abs(X)
for i in range(K):
    X_ = min(X, abs(X-D))
    if X == X_:
        X = abs(X_ - (K - i)%2*D)
        break
    X = X_
print(X)


### FIXED CODE ###

X, K, D = map(int, input().split())
X = abs(X)
if X // D <= K:
    print(min(abs(X % D - (K - (X // D))%2*D), abs(X % D + (K - (X // D))%2*D)))
else:
    print(min(abs(X - K*D), abs(X + K*D)))
### BUGGY CODE ###

def frog2(N,h,k):
    dp=[0]*(N)
    dp[0]=0

    for i in range(1,N):
        mn=float('inf')
        for j in range(1,k+1):
            if i-j>=0:
                mn=min(mn,abs(h[i]-h[i-j])+dp[i-j])
        dp[i]=mn
    return dp[N-1]



N,k=map(int,input().split())
h=list(map(int,input().split()))
print(frog2(N,h,k))

### FIXED CODE ###

import sys
def frog2(N,h,k):
    dp=[sys.maxsize-1]*N
    dp[0]=0
    for i in range(N):
        for j in range(i+1,i+k+1):
            if j<N:
                dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))
    return dp[N-1]

N,k=map(int,input().split())
h=list(map(int,input().split()))
print(frog2(N,h,k))
### BUGGY CODE ###

from fractions import gcd

def main():
    N=int(input())
    A=list(map(int,input().split()))
    lcm=A[0]
    for i in range(1,N):
        lcm=lcm*A[i]//(gcd(lcm,A[i]))

    ans=0
    for i in range(0,N):
        ans=(ans+(lcm//A[i])%(10**9+7))%(10**9+7)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from fractions import gcd
    import sys
    input=sys.stdin.readline
    N=int(input())
    A=list(map(int,input().split()))
    lcm=A[0]
    for a in A:
        lcm=lcm*a//(gcd(lcm,a))

    ans=0
    for a in A:
        ans=ans+(lcm//a)
    print(ans%(10**9+7))

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

n=int(input())
lst=list(map(int,input().split()))
count=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):              
            a=lst[i]
            b=lst[j]
            c=lst[k]
            if a<b+c and b<c+a and c<a+b:
                    count+=1
print(count)


### FIXED CODE ###

import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(0,n-2):
    for j in range(i+1,n-1):
        x=l[i]+l[j]
        y=bisect.bisect_left(l,x)-j-1        
        ans+=y
print(ans)
### BUGGY CODE ###

import collections

n = int(input())

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

a.sort()

dp = [True] * n

for i in range(len(a)):
    if dp[i] == True:
        for j, x in enumerate(a[i+1:], 1):
            if dp[i + j] == True:
                if a[i + j] % a[i] == 0:
                    dp[i + j] = False

num_dict = dict(collections.Counter(a))

result = [x for x, y in zip(a, dp) if (y == True) and (num_dict[x] == 1)]

print(len(result))

### FIXED CODE ###

n = int(input())

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

a.sort()

dp = [True] * (a[-1] + 1)

ans = 0

m = a[-1]

for i, x in enumerate(a[:-1]):
    if not a[i+1] == x and dp[x]:
        ans += 1
    for b in range(x, m + 1, x):
        dp[b] = False

if dp[a[-1]]:
    ans += 1

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

S = input()
Q = int(input())
for i in range(Q):
  Query_i = list(map(str, input().split()))
  if Query_i[0]=='1':
    S = S[::-1]
  elif Query_i[1] == '1':
    S = Query_i[2] + S
  else:
    S = S + Query_i[2]
print(S)

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
flip = False # False: left side is the head
for i in range(Q):
  Query_i = list(map(str, input().split()))
  if Query_i[0]=='1':
    flip = not flip
  elif Query_i[1] == '1' and not flip:
    S.appendleft(Query_i[2])
  elif Query_i[1] == '1' and flip:
    S.append(Query_i[2])
  elif Query_i[1] == '2' and not flip:
    S.append(Query_i[2])
  elif Query_i[1] == '2' and flip:
    S.appendleft(Query_i[2])
if flip:
  S.reverse()
print(''.join(S))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**9
dp = [INF] * N
dp[0] = 0
for i in range(N):
    for k in range(K):
        if i + k +1 < N:
            #print(i, i +k+1, h[i], h[i+k+1])
            dp[i+k+1] = min(dp[i+k+1], dp[i]+abs(h[i] - h[i+k+1]))
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**9
dp = [INF] * N
dp[0] = 0
for i in range(N):
    for k in range(1, K+1):
        if i + k < N:
            dp[i+k] = min(dp[i+k], dp[i]+abs(h[i] - h[i+k]))
print(dp[N-1])