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

N = int(input())
#a,b = map(int,input().split())
A = list(map(int,input().split()))
#A = [int(input()) for i in range(N)]
#A = [list(map(int,input().split())) for i in range(N)]
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b):
    gcda = gcd(a,b)
    return a*b//gcda
def lcmlist(lista):
    if len(lista) == 1:
        return lista[0]
    else:
        lista2 = []
        for i in range(1,len(lista),2):
            lista2.append(lcm(lista[i],lista[i-1]))
        if len(lista)%2 != 0:
            lista2.append(lista[-1])
        from functools import reduce
        return reduce(lcm,lista2)
mod = 10**9 + 7
lcml = lcmlist(A)
ans = 0
for i in A:
    ans = (ans + lcml//i)%mod
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
LCM = 1
for i in A:
    GCD = gcd(LCM,i)
    LCM = LCM*i//GCD
ans = 0
for i in A:
    ans += LCM//i
print(ans%mod)
### BUGGY CODE ###

h=0
a=list(input())
if len(a)==1:
  print(0)
else:
  for i in range(1,len(a)):
    if int(a[i-1])==int(a[i]):
      if int(a[i])==0:
        b=1
      else:
        b=0
      a.pop(i)
      a.insert(i,b)
      h+=1
  print(h)

### FIXED CODE ###

a = list(input())
s = a[0]
count = 0
if s == "0":
    for i in range(1, len(a)):
        if int(a[i]) != i % 2:
            count += 1
elif s == "1":
    for i in range(1, len(a)):
        if int(a[i]) != (i + 1) % 2:
            count += 1
print(count)
### BUGGY CODE ###

import sys
import numpy as np
import math  # gcdもあるよ
import collections
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化

def main():
    n = int(sys.stdin.readline())
    a = list(map(int,sys.stdin.readline().split()))
    q = int(sys.stdin.readline())
    queue = [list(map(int,sys.stdin.readline().split())) for _ in range(q)]
    count = collections.Counter(a)
    #print(count)
    #print(list(count))
    for b, c in queue:
        if  b in count:
            if c in count:
                count[c] += count[b]
                del count[b]
            else:
                count[c] = count[b]
                del count[b]
        ans = 0
        for k in count:
            ans += k * count[k]
        print(ans) 
    
    
    return 0

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import numpy as np
import math  # gcdもあるよ
import collections
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化

def main():
    n = int(sys.stdin.readline())
    a = list(map(int,sys.stdin.readline().split()))
    q = int(sys.stdin.readline())
    queue = [list(map(int,sys.stdin.readline().split())) for _ in range(q)]
    count = collections.Counter(a)
    #print(count)
    #print(list(count))
    ans = 0
    for k in count:
        ans += k * count[k]
    for b, c in queue:
        if  b in count:
            if c in count:
                count[c] += count[b]
                ans += (c - b) * count[b]
                del count[b]
            else:
                count[c] = count[b]
                ans += (c - b) * count[b]

                del count[b]
        print(ans)
    
    
    return 0

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

import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

## 計算量: H*N

H, N = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(N)]

inf = float("inf")
dp = [inf for i in range(H+1)] ## i: 体力
dp[0] = 0

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

### FIXED CODE ###

#import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

## 計算量: H*N

H, N = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(N)]

inf = float("inf")
dp = [inf for i in range(H+1)] ## i: 体力
dp[0] = 0

for i in range(1, H+1):
  for j in range(N):
    dp[i] = min(dp[i], dp[max(i - AB[j][0], 0)] + AB[j][1])
    
print(dp[H])
### BUGGY CODE ###

a=[]
m1,m2=0,0
for _ in range(input()):
    n=input()
    a.append(n)
    if n>m1:
        m2=m1
        m1=n
    elif n>m2:
        m2=n
for i in a:
    if i==m1:
        print m2
    else:
        print m1


### FIXED CODE ###

a=[]
m1,m2=0,0
ct=0
t=input()
for i in range(t):
    n=input()
    a.append(n)
    if n>m1:
        m2=m1
        m1=n
        ct=i
    elif n>m2:
        m2=n
for i in range(t):
    if i==ct:
        print m2
    else:
        print m1
### BUGGY CODE ###

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

th=10**18
ans=1
flag=0
for i in a:
    if i==0:
        flag=1
        break
    ans*=i
if(flag==1):
    print(0)
elif ans<=th:
    print(ans)
else:
    print("-1")

### FIXED CODE ###

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

aa=sorted(a)
th=10**18
ans=1

for i in range(len(aa)):
    if aa[i]==0:
        print(0)
        break
    ans*=aa[i]
    if ans>th:
        print(-1)
        break
    if i==len(aa)-1:
        print(ans)
### BUGGY CODE ###

import itertools

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

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW))
    NEXT=[now%mod for now in NOWSUM]
    #print(NEXT)

    for j in range(a+1,K+1):
        NEXT[j]-=NOWSUM[j-a-1]%mod


    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K]%mod)

### FIXED CODE ###

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

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for i in range(N):
    NEXT=[0]*(K+1)
    NOWSUM=[0]
    for n in NOW:
        NOWSUM.append(NOWSUM[-1]+n)
        
    for j in range(K+1):
        NEXT[j]=(NEXT[j]+NOWSUM[j+1]-NOWSUM[max(0,j-A[i])])%mod

    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K])
### BUGGY CODE ###

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

L,R=map(int, input().split())

ans = 2 * (10**9)

for i in range(L,R+1):
    for j in range(i+1,R+1):
        ans = min(ans, (i*j)%2019)

print(ans)

### FIXED CODE ###

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

L,R=map(int, input().split())

ans = 2 * (10**9)

for i in range(L,min(R+1,L+2019)):
    for j in range(i+1,min(R+1,L+2019)):
        ans = min(ans, ((i%2019)*(j%2019)%2019))

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

from collections import deque

def main():
    N=int(input())
    A=list(map(int, input().split()))
    B=list(map(int, input().split()))
    q = deque()
    cq = deque()
    q.appendleft(B)
    cq.appendleft(0)

    while len(q) > 0:
        b = q.pop()
        c = cq.pop()
        if b == A:
            print(c)
            break
        else:
            for i in range(N):
                _tmp = b[0:N]
                _tmp[i] = b[i] - b[i-1 if i>=1 else N-1] - b[i+1 if i<N-1 else 0]
                if _tmp[i] >= 1:
                    q.appendleft(_tmp)
                    cq.appendleft(c+1)
    else:
        print(-1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N=int(input())
    A=list(map(int, input().split()))
    B=list(map(int, input().split()))

    count = 0
    prev_count = -1
    while count!=prev_count:
        prev_count = count
        for i in range(N):
            d = B[i-1 if i>=1 else N-1] + B[i+1 if i<N-1 else 0]
            c = (B[i]-A[i]) // d
            B[i] -= d * c
            count += c

    if A == B:
        print(count)
    else:
        print(-1)

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

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

tmpList=QsList[:]
tmpList.sort()

cnt=0
tmp=0
AnsList=QsList[:]
for i in QsList:
  tmp=int(QsList.index(i))+1
  a=int(tmpList.index(i))
  a=int(a)
  AnsList[a]=tmp
  
for i in AnsList:
  print(i,end=" ")

### FIXED CODE ###

n=int(input())
a = list(map(int,input().split()))
enumerate(a,1)
b=sorted(range(len(a)), key=lambda k: a[k])
for i in range(len(b)):
  print(b[i]+1)
### BUGGY CODE ###

n,a,b=map(int,input().split())
h=[-1*int(input()) for _ in range(n)]

import heapq  # heapqライブラリのimport
#heapq.heapify(a)  # リストを優先度付きキューへ
#heapq.heappop(a)  # 最小値の取り出し
#heapq.heappush(a, -2)

heapq.heapify(h)

#直撃a、爆風b
cnt=1
while 1:
    tmp=heapq.heappop(h)*(-1)
    tmp=tmp-a+b
    heapq.heappush(h,(-1)*tmp)

    tmp=heapq.heappop(h)*(-1)
    
    if tmp-b*cnt<=0:
        print(cnt)
        break
    heapq.heappush(h,tmp*(-1))
    cnt+=1






### FIXED CODE ###

n,a,b=map(int,input().split())
h=[int(input()) for _ in range(n)]

#二部探索

ll=0
rr=10**9+1
ab=a-b
while ll<rr:
    half=(ll+rr)//2

    cnt=0
    for hh in h:
        if hh>b*half:
            cnt+=(-1*((-1*(hh-b*half))//ab))
    
    if cnt>half:
        ll=half+1
    elif cnt<half:
        rr=half
    else:
        print(half)
        exit()
print(ll)
### BUGGY CODE ###

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

def main():
  for i in range(k+1, n+1):
    sum_prev, sum_next = (1, 1)

    for j in range(i-k-1, i-1):
      sum_prev *= int(items[j])
      sum_next *= int(items[j+1])

    if (sum_prev < sum_next):
      print("Yes")
    else:
      print("No")

main()


### FIXED CODE ###

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

for i in range(k, n):
  if (int(items[i]) > int(items[i-k])):
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

from collections import deque
N,M = map(int,input().split())
l = [[] for _ in range(N+1)]
 
for _ in range(M):
  a,b = map(int,input().split())
  l[a].append(b)
  l[b].append(a)
ans = 0
check = [0]*(N+1)
for i in range(1,N+1):
  st = deque([i])
  check[i] = 1
  while st:
    s = st.popleft()
    for t in l[s]:
      if check[t] == 0:
        check[t] = 1
        st.append(t)
  ans = max(ans,N-sum(check))
print(ans)

### FIXED CODE ###

from collections import deque
N,M = map(int,input().split())
l = [[] for _ in range(N+1)]
 
for _ in range(M):
  a,b = map(int,input().split())
  l[a].append(b)
  l[b].append(a)

check = [0]*(N+1)
cnt = 0
for i in range(1,N+1):
  if check[i] == 1:
    continue
  st = deque([i])
  check[i] = 1
  while st:
    s = st.popleft()
    for t in l[s]:
      if check[t] == 0:
        check[t] = 1
        st.append(t)
      continue
  cnt += 1

print(cnt-1)
### BUGGY CODE ###

import sys 

N,M  = map(int,input().split())
     
a = [[0 for i in range(2)] for j in range(M)]
b = []     
for l in range(M):
  a[l][0] , a[l][1] = map(int,input().split())
  if a[l][0] == 1:
    b.append(l)

res = 'IMPOSSIBLE'

for i in b:
  for k in range(M):
    if a[k][0] == a[i][1] and a[k][1] == N:
         res = 'POSSIBLE'
         break

print (res)


### FIXED CODE ###

import sys 

N,M  = map(int,input().split())
     
a = [[0 for i in range(2)] for j in range(M)]
b = [] 
c = []

for i in range(M):
  a[i][0] , a[i][1] = map(int,input().split())
  first, second = a[i][0],a[i][1]
  if first == 1:
    b.append(second)
  if second == N:
    c.append(first)

b_set = set(b)
c_set = set(c)

if list(b_set & c_set) is None or len(list(b_set & c_set)):
  res = ('POSSIBLE')
else:
  res = ('IMPOSSIBLE')

print(res)
### BUGGY CODE ###

import itertools
import math
N = int(input())
for n in range(1, N+1):
  ans = 0
  n_max = int(math.sqrt(n))
  l = [i for i in range(1, n_max)]
  for c in itertools.combinations_with_replacement(l, 3):
    if n == c[0]**2 + c[1]**2 + c[2]**2 + c[0]*c[1] + c[0]*c[2] + c[1]*c[2]:
      if len(set(c)) == 1:
        ans += 1
      elif len(set(c)) == 2:
        ans += 3
      elif len(set(c)) == 3:
        ans += 6
  print(ans)

### FIXED CODE ###

import itertools
import math
import numpy as np

N = int(input())

n_max = int(math.sqrt(N))
l = [i for i in range(1, n_max)]
score = np.zeros([10000]).astype(np.uint8)
for c in itertools.combinations_with_replacement(l, 3):
  sum = c[0]**2 + c[1]**2 + c[2]**2 + c[0]*c[1] + c[0]*c[2] + c[1]*c[2]
  if sum <= 10000:
    if len(set(c)) == 3:
      score[sum-1] += 6
    elif len(set(c)) == 2:
      score[sum-1] += 3
    else:
      score[sum-1] += 1
    
for n in range(1, N+1):
  ans = 0
  print(score[n-1])
### BUGGY CODE ###

MOD = 10**9+7
t_p= []
t_rp = []

def g(r,c):
    ans = 0
    for i in range(r+1):
        ans += f(i+1,c)
        ans %= MOD
    return ans

def f(r,c):
    return (p(r+c) * rp(r) * rp(c)) % MOD

def p(n):
    if t_p[n] == 0:
        ans = 1
        for i in range(2,n+1):
            ans *= i
            ans %= MOD
        t_p[n] = ans
    return t_p[n]

def rp(n):
    if n == 0:
        return 1
    if t_rp[n] == 0:
        t_rp[n] = mod_inv(p(n), MOD)
    return t_rp[n]

def extgcd(a,b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2]//w[2]
        ra = w
        wa = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = ra
        w = wa
    #[x,y]
    return [w[0], w[1]]

def mod_inv(a,m):
    x = extgcd(a, m)[0]
    return (m+x%m)%m

r1,c1, r2,c2 = map(int,input().split())
t_p = [0 for _ in range(r2+c2+3)]
t_rp = [0 for _ in range(max(r2,c2)+2)]
ans = g(r2,c2) - g(r1-1,c2) - g(r2,c1-1) + g(r1-1,c1-1)
ans %= MOD
print (ans)

### FIXED CODE ###

MOD = 10**9+7
p= []
rp = []

def g(r,c):
    ans = 0
    if r > c:
        r,c = c,r
    for i in range(r+1):
        ans += f(i+1,c)
        ans %= MOD
    return ans

def f(r,c):
    return (p[r+c] * rp[r] * rp[c]) % MOD

def extgcd(a,b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2]//w[2]
        ra = w
        wa = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = ra
        w = wa
    #[x,y]
    return [w[0], w[1]]

def mod_inv(a,m):
    x = extgcd(a, m)[0]
    return (m+x%m)%m

r1,c1, r2,c2 = map(int,input().split())
p = [0 for _ in range(r2+c2+3)]
rp = [0 for _ in range(max(r2,c2)+2)]

p[0] = 1
p[1] = 1
rp[0] = 1
rp[1] = 1
for i in range(2,c2+r2+3):
    p[i] = (p[i-1] * i) % MOD

for i in range(2,max(r2,c2)+2):
    rp[i] = mod_inv(p[i], MOD)

ans = g(r2,c2) - g(r1-1,c2) - g(r2,c1-1) + g(r1-1,c1-1)
ans %= MOD
print (ans)
### BUGGY CODE ###

import numpy as np
N,C=map(int,input().split())
 
def get_unique_list(seq):
  seen = []
  return [x for x in seq if x not in seen and not seen.append(x)]
 
Record=np.empty((0,3), int)
 
for i in range(N):
  lis=list(map(int,input().split()))
  n=np.array(lis)
  Record=np.append(Record,[n],axis=0)
#print(Record)
 
 
newRecord=np.empty((0,3), int)
for c in range(C):
  Recordi=np.empty((0,3), int)
  for i in range(N):
    if Record[i][2]==c+1:
      Recordi=np.append(Recordi,[Record[i]],axis=0)
  
  sort_Recordi=Recordi[np.argsort(Recordi[:,0])]
  #print(sort_Recordi)
  for j in range(len(sort_Recordi)-1):
    if sort_Recordi[j][1]==sort_Recordi[j+1][0]:
      sort_Recordi[j][1]=sort_Recordi[j+1][1]
      sort_Recordi[j+1][0]=sort_Recordi[j][0]
  sort_Recordi_u=set(map(tuple,sort_Recordi))
  sort_Recordi_u=np.array(list(sort_Recordi_u))
  #print(sort_Recordi_u)
  for k in range(len(sort_Recordi_u)):
    newRecord=np.append(newRecord,[sort_Recordi_u[k]],axis=0)
    
      
#print(newRecord)
nofc=np.zeros(10**5+1,dtype=int)
 
for a in newRecord:
  vec=np.ones(a[1]-a[0]+1,dtype=int)
  nofc[a[0]:a[1]+1]+=vec
#print(vec)
#print(nofc[:13])
print(int(max(nofc)))

### FIXED CODE ###

import numpy as np
N,C=map(int,input().split())

nofc=np.zeros((C,10**5),dtype=int)

for i in range(N):
  s,t,c=map(int,input().split())
  vec=np.ones(t-s+1,dtype=int)
  nofc[c-1][s-1:t]=vec
print(int(max(np.sum(nofc,axis=0))))
### BUGGY CODE ###

import numpy as np

N = int(input())
n = [int(x) for x in input().split()]
n=np.array(n)

a=1
for i in range(1,N):
    if np.min(n[:i]) > n[i] : a+=1   
print(a)

### FIXED CODE ###

import numpy as np

N = int(input())
n = [int(x) for x in input().split()]
n=np.array(n)

a=1
pos=0
for i in range(1,N):
    if n[pos] > n[i] :
        a+=1
        pos=i
print(a)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

class Sparsetable:
    def __init__(self, B):
        self.B = B
        self.N = len(B)
        A = list(range(self.N))
        self.bn = self.N.bit_length()
        self.res = [[None]*self.bn for _ in range(self.N)]
        for i in range(self.N):
            self.res[i][0] = A[i]
        
        for dn in range(1, self.bn):
            rn = 1<<(dn-1)
            for h in range(self.N-2*rn+1):
                self.res[h][dn] = self.spf(self.res[h][dn-1], self.res[h+rn][dn-1])
    
    def spf(self, x, y):
        if self.B[x] > self.B[y]:
            return x
        return y
    
    def query(self, h1, h2):
        h2 -= 1
        hl = h2-h1+1
        bh = hl.bit_length()-1
        rh = 1<<bh
        return self.spf(self.res[h1][bh], self.res[h2-rh+1][bh])
    

N, M = map(int, readline().split())
A = [0] + list(map(int, readline().split())) + [0]
for i in range(1, N):
    A[i] += A[i-1]

B = [list(map(int, readline().split())) for _ in range(N)]
B = list(map(list, zip(*B)))

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

for j in range(M):
    St = Sparsetable(B[j])
    stack = [(0, N)]
    
    while stack:
        l, r = stack.pop()
        
        am = St.query(l, r)
        b = B[j][am]
        table[l][am] += b
        table[l][r] -= b
        table[am+1][am] -= b
        table[am+1][r] += b
        if am != l:
            stack.append((l, am))
        if am+1 != r:
            stack.append((am+1, r))
    
for i in range(1, N+1):
    for j in range(N+1):
        table[i][j] += table[i-1][j]
for j in range(1, N+1):
    for i in range(N+1):
        table[i][j] += table[i][j-1]

ans = 0
for i in range(N):
    for j in range(i+1, N+1):
        ans = max(ans, table[i][j-1] - (A[j-1] - A[i]))

print(ans)


### FIXED CODE ###

import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
A = [0] + list(map(int, readline().split()))
for i in range(1, N):
    A[i] += A[i-1]

INF = 10**9+7
B = [list(map(int, readline().split())) for _ in range(N)] + [[INF]*M] + [[0]*M]
right = [[0]*M for _ in range(N)]

for m in range(M):
    L = list(range(N))
    L.sort(key = lambda x: B[x][m])
    RR = list(range(1, N+3))
    LL = list(range(-1, N+1))
    for vn in L:
        vn += 1
        right[vn-1][m] = RR[vn]-1
        RR[LL[vn]] = RR[vn]
        LL[RR[vn]] = LL[vn]

diff = [0]*(N+1)
for m in range(M):
    diff[0] += B[0][m]
    pre = B[0][m]
    for i in range(1, N):
        if B[i][m] > pre:
            diff[i] += B[i][m]-pre
            pre = B[i][m]

offset = 0
ans = 0
for l in range(N):
    offset += diff[l]
    for m in range(M):
        if B[l][m] < B[l-1][m]:
            oldr = right[l-1][m]
            diff[oldr] -= B[oldr][m] - B[l-1][m]
            offset += B[l][m] - B[l-1][m]
            cnt = l
            while cnt < N and right[cnt][m] <= oldr:
                rcm = right[cnt][m]
                diff[rcm] += B[rcm][m] - B[cnt][m]
                cnt = rcm
    ans = max(ans, offset)
    roff = offset
    for r in range(l+1, N):
        roff += diff[r]
        ans = max(ans, roff - (A[r]-A[l]))
        #print(l, r, roff - (A[r] - A[l]))

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

from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=int(1e9)+7

###############################################################################\n=17
n=int(input())
A=INPUT()
sum=0
for i in range(n):
    for j in range(i+1,n):
        sum+=(A[i]*A[j])%J
        sum%=J
print(sum%J)


### FIXED CODE ###

from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=int(1e9)+7

###############################################################################\n=17
n=int(input())
A=INPUT()
sum=0
for i in range(n):
    sum+=A[i]
sum=sum*sum

s=0
for i in range(n):
    s+=A[i]**2

ans=(sum-s)//2
ans%=J
print(ans)
### BUGGY CODE ###

N=int(input())
strings=sorted([sorted(list(input())) for i in range(N)])
cnt=0
for i in range(N-1):
    for k in range(1,N-i):
        if strings[i]==strings[i+k]:
            cnt+=1
        else:
            break
print(cnt)

### FIXED CODE ###

N=int(input())
strings=sorted([sorted(list(input())) for i in range(N)])
strings.append("000")
cnt=0
i=0
same=1
while i<N:
    if strings[i]==strings[i+1]:
        same+=1
    else:
        cnt+=same*(same-1)/2
        same=1
    i+=1
print(int(cnt))
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
b = 1
for a in l:
    b = b * a 
if b > 10 ** 18:
    b = -1
print(b)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def input():
    return sys.stdin.readline()[:-1]
n = int(input())
l = list(map(int, input().split(" ")))
output = 1

if 0 in l:
    print(0)
    sys.exit()

for i in range(n):
    output = output * int(l[i])
    if output > 10 ** 18:
        output = -1
        break
print(output)
### BUGGY CODE ###

import collections
n=input()
s=[]
for i in range(len(n)-1):
  s.append(n[i])
  for j in range(i+1,len(n)):
    s.append(n[j])
    
    t=collections.Counter(s)
    
    d=t.most_common()[0][1]  
    
    if (j-i+1)/d<2:
      print(i+1,j+1)
      exit()
  s=[] 
print("-1 -1")

### FIXED CODE ###

n=input()
for i in range(len(n)-1):
  if n[i]==n[i+1]:
    print(i+1,i+2)
    exit()
for i in range(len(n)-2):
  if n[i]==n[i+2]:
    print(i+1,i+3)
    exit()
print(-1,-1)
### BUGGY CODE ###

N,M,L = map(int,input().split())
INF = (500, 10**9)
dist = [[INF if i != j else (0,0) for i in range(N)] for j in range(N)]
edge = [[] for i in range(N)]
for i in range(M):
	A,B,C = map(int,input().split())
	if C <= L:
		edge[A-1].append((B-1, C))
		edge[B-1].append((A-1, C))

import heapq as hq
for i in range(N):
	searched = [False for j in range(N)]
	n = i
	while n != None:
		searched[n] = True
		for e in edge[n]:
			if searched[e[0]]:
				continue
			d = dist[i][n]
			n2, d2 = e[0], e[1]
			if d[1] + d2 > L:
				new_d = (d[0] + 1, d2)
			else:
				new_d = (d[0], d[1] + d2)
			dist[i][n2] = min(dist[i][n2], new_d)
		n = None
		m = INF
		for j in range(N):
			if not searched[j] and dist[i][j] < m:
				n = j
				m = dist[i][j]


Q = int(input())
for q in range(Q):
	s,t = map(int,input().split())
	print(dist[s-1][t-1][0] if dist[s-1][t-1] != INF else -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M,L = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*M]
Q = int(input())
ST = [list(map(int,input().split())) for _ in [0]*Q]


INF = (L+1)*N
d = [[INF]*N for _ in [0]*N]
for i in range(N):
    d[i][i] = 0
for a,b,c in ABC:
    a-=1;b-=1
    d[a][b] = c
    d[b][a] = c

def Warshall_Floyd(d,N=None):
    if N==None : N = len(d)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])

Warshall_Floyd(d,N)

d2 = [None]*N
for i,row in enumerate(d):
    d2[i] = [1 if e<=L else INF for e in row]
    d2[i][i] = 0

Warshall_Floyd(d2,N)

for s,t in ST:
    s-=1;t-=1
    ans = (d2[s][t]%INF)-1
    print(ans)