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

import itertools
N = int(input())
L = list(map(int, input().split()))
res = 0
for comb in list(itertools.combinations(L, 3)):
    comb = sorted(comb)
    if comb[0] + comb[1] > comb[2]:
        res += 1
print(res)


### FIXED CODE ###

from bisect import bisect_left
N = int(input())
l = list(map(int, input().split()))
l.sort()
res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        t = l[i] + l[j]
        idx = bisect_left(l, t)
        res += idx-j-1
print(res)
### BUGGY CODE ###

N,K=map(int,input().split())
num_list=[x for x in range(N+1)]
answer=0
count=N-K+2
for y in range(K,N+2):
    min=sum(num_list[:y])
    max=sum(num_list[-y:])
    answer+=max-min+1

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


### FIXED CODE ###

N,K=map(int,input().split())
answer=0
count=N-K+2
for y in range(K,N+2):
    min=int(y*(0+y-1)/2)
    max=int(y*(N-y+1+N)/2)
    answer+=(max+1-min)
print(answer%(10**9+7))
### BUGGY CODE ###

from collections import Counter

S = input()

"""
counts = Counter()
total = 0
for d in S:
    d = int(d)
    nextCounts = Counter()
    nextCounts[d] += 1
    for k, v in counts.items():
        nextCounts[(10 * k + d) % 2019] += v

    counts = nextCounts
    total += counts[0]
    #print(counts)

print(total)

"""

"""
def modInverse(a, m):
    m0 = m
    y = 0
    x = 1

    if m == 1:
        return 0

    while a > 1:

        # q is quotient
        q = a // m

        t = m

        # m is remainder now, process
        # same as Euclid's algo
        m = a % m
        a = t
        t = y

        # Update x and y
        y = x - q * y
        x = t

    # Make x positive
    if x < 0:
        x = x + m0

    return x
"""


#div10 = modInverse(10, 2019)

div10 = 202
#m = 1
mInv = 1

off = 0
counts = Counter()
total = 0
for d in S:
    d = int(d)
    off = 10 * off + d
    #m *= 10
    mInv = (mInv * div10) % 2019
    #assert modInverse(m, 2019) == mInv
    counts[((d - off) * mInv) % 2019] += 1
    total += counts[((0 - off) * mInv) % 2019]

print(total)


### FIXED CODE ###

from collections import Counter

S = input()

"""
counts = Counter()
total = 0
for d in S:
    d = int(d)
    nextCounts = Counter()
    nextCounts[d] += 1
    for k, v in counts.items():
        nextCounts[(10 * k + d) % 2019] += v

    counts = nextCounts
    total += counts[0]
    #print(counts)

print(total)

"""

"""
def modInverse(a, m):
    m0 = m
    y = 0
    x = 1

    if m == 1:
        return 0

    while a > 1:

        # q is quotient
        q = a // m

        t = m

        # m is remainder now, process
        # same as Euclid's algo
        m = a % m
        a = t
        t = y

        # Update x and y
        y = x - q * y
        x = t

    # Make x positive
    if x < 0:
        x = x + m0

    return x
"""


#div10 = modInverse(10, 2019)

div10 = 202
#m = 1
mInv = 1

off = 0
counts = [0 for i in range(2019)]
total = 0
for d in S:
    d = int(d)
    off = (10 * off + d) % 2019
    #m *= 10
    mInv = (mInv * div10) % 2019
    #assert modInverse(m, 2019) == mInv
    counts[((d - off) * mInv) % 2019] += 1
    total += counts[((0 - off) * mInv) % 2019]

print(total)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
items = list(map(int, input().split()))
items.sort(reverse=True)
for _ in range(M):
	items[0] //= 2
	items.sort(reverse=True)
print(sum(items))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
items = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(items)
for _ in range(M):
	tmp = heapq.heappop(items)
	heapq.heappush(items, int(tmp/2))
print(-sum(items))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)
N,m,k = [int(x) for x in input().split()]
p = []
q = []
roots = [0]*(N+1)
rootmatome = [0]*(N+1)
tonari = [0]*(N+1)
dame = [0]*(N+1)
for i in range(m):
    p.append(list(map(int, input().split())))
for i in range(k):
    q.append(list(map(int, input().split())))
par = []
for i in range(N+1):
    par.append(i)
#from functools import lru_cache
#@lru_cache(maxsize=1000)
def root(x):
    if par[x] == x:
        return x
    return root(par[x])
def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    par[rx] = ry
def same(x,y):
    rx = root(x)
    ry = root(y)
    return rx == ry
for i in range(m):
    unite(p[i][0],p[i][1])
for i in range(1,N+1):
  roots[i] = root(i)
for i in range(1,N+1):
    rootmatome[roots[i]] += 1
for i in range(m):
    tonari[p[i][0]] += 1
    tonari[p[i][1]] += 1
for i in range(k):
    if roots[q[i][0]] == roots[q[i][1]]:
        dame[q[i][0]] += 1
        dame[q[i][1]] += 1
for i in range(1,N+1):
    print(rootmatome[roots[i]] - tonari[i] - dame[i] - 1,end=" ")          

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N,m,k = [int(x) for x in input().split()]
p = []
q = []
roots = [0]*(N+1)
rootmatome = [0]*(N+1)
tonari = [0]*(N+1)
dame = [0]*(N+1)
for i in range(m):
    p.append(list(map(int, input().split())))
for i in range(k):
    q.append(list(map(int, input().split())))
par = []
for i in range(N+1):
    par.append(i)
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])#この一文で早くなる
    return root(par[x])
def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    par[rx] = ry
for i in range(m):
    unite(p[i][0],p[i][1])
for i in range(1,N+1):
  roots[i] = root(i)
for i in range(1,N+1):
    rootmatome[roots[i]] += 1
for i in range(m):
    tonari[p[i][0]] += 1
    tonari[p[i][1]] += 1
for i in range(k):
    if roots[q[i][0]] == roots[q[i][1]]:
        dame[q[i][0]] += 1
        dame[q[i][1]] += 1
for i in range(1,N+1):
    print(rootmatome[roots[i]] - tonari[i] - dame[i] - 1,end=" ")
### BUGGY CODE ###

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

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

ans = 0
for i in range(len(a_list) - k + 1):
    for j in range(len(a_list) - 1, k + i - 2, -1):
        if(a_list[j] - a_list[i] != 0):
            ans += (a_list[j] - a_list[i]) * combinations_count(j-i-1, k-2)
ans %= 1000000007
print(ans)


### FIXED CODE ###

MOD = 1000000007
# 二項係数
class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD

com = COM(100000, MOD)
n, k = map(int, input().split())
a_list = sorted(list(map(int, input().split())))

ans = 0
if k == 1:
    print(0)
else:
    for i in range(1, n+1):
        if i >= k:
            ans += a_list[i-1] * com.calc_COM(i-1, k-1)
        if n-i >= k-1:
            ans -= a_list[i-1] * com.calc_COM(n-i, k-1)
    ans %= MOD
    print(ans)
### BUGGY CODE ###

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

L = [i+A[i] for i in range(N)]
R = [i-A[i] for i in range(N)]

p = {}
m = {}
for i in range(N):
    if L[i] not in p:
        p[L[i]] = 1
    else:
        p[L[i]] += 1
for i in range(N):
    if R[i] not in m:
        m[R[i]] = 1
    else:
        m[R[i]] += 1

lower = min(min(p), min(m))
upper = max(max(p), max(m))
ans = 0
for x in range(lower, upper + 1):
    if x in p and x in m:
        ans += p[x] * m[x]

print(ans)

### FIXED CODE ###

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

L = [i+A[i] for i in range(N)]
R = [i-A[i] for i in range(N)]

p = {}
m = {}
for i in range(N):
    if L[i] not in p:
        p[L[i]] = 1
    else:
        p[L[i]] += 1
for i in range(N):
    if R[i] not in m:
        m[R[i]] = 1
    else:
        m[R[i]] += 1

lower = max(min(p), min(m))
upper = min(max(p), max(m))
ans = 0
for x in range(lower, upper + 1):
    if x in p and x in m:
        ans += p[x] * m[x]

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

def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + ord(s[i])) % mod
    return h
# RH前に、必要な長さの最大値分のpow-tableを計算しておく
def setup_pw(l):
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
    return pw
def get(h, b, l, r):
    return (h[r] - h[l] * b[r-l]) % mod

N = int(input())
S = input()
mod = 1000000007
base = 37
h1 = rolling_hash(S)
b1 = setup_pw(N)
Max = N // 2
broke = False
for i in range(Max-1):
    for j in range(N-2*(Max-i)+1):
        for k in range(N-2*(Max-i)-j+1):
            if get(h1,b1,j,(Max-i)+j) == get(h1,b1,j+(Max-i)+k,2*(Max-i)+j+k):
                print(Max-i)
                broke = True
                break
        if broke == True:
            break
    if broke == True:
        break
if broke == False:
    print('0')

### FIXED CODE ###

def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + ord(s[i])) % mod
    return h
def setup_pw(l):
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
    return pw
def get(h, b, l, r):
    return (h[r] - h[l] * b[r-l]) % mod

def check_bisect(l,h1,b1,h2,b2):
    for j in range(N-2*l+1):
        a1 = get(h1,b1,j,l+j)
        a2 = get(h2,b2,j,l+j)
        for k in range(N-2*l-j+1):
            if a1 == get(h1,b1,j+l+k,2*l+j+k) and a2 == get(h2,b2,j+l+k,2*l+j+k):
                return True
    return False

N = int(input())
S = input()
mod = 1000000007
base = 37
h1 = rolling_hash(S)
b1 = setup_pw(N)
base = 401
h2 = rolling_hash(S)
b2 = setup_pw(N)
left = 1
right = N // 2
finish = False
if N <= 26:
    s = set(list(S))
    if N <= 3:
        if len(s) < N:
            print('1')
        else:
            print('0')
        finish = True
    else:
        if len(s) == N:
            print('0')
            finish = True
while finish == False:
    if left == right:
        print(left)
        finish = True
    elif right - left == 1:
        if check_bisect(right,h1,b1,h2,b2):
            print(right)
        else:
            print(left)
        finish = True
    else:
        mid = (left+right) // 2
        if check_bisect(mid,h1,b1,h2,b2):
            left = mid
        else:
            right = mid - 1
### BUGGY CODE ###

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

from collections import Counter
c = Counter(l)

from math import factorial
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

num = []
tot = 0
for i,j in c.items():
    if j >= 2:
        tmp1 = combinations_count(j,2)
        tot += tmp1
    else:
        tmp1 = 0
    if j >= 3:
        tmp2 = combinations_count(j-1,2)
    else:
        tmp2 = 0
    num.append([i,tmp1,tmp2])

for x in range(n):
    for y in range(len(c)):
        if num[y][0] == l[x]:
            print(tot - num[y][1] + num[y][2])


### FIXED CODE ###

n = int(input())
l = [int(x) for x in input().split()]

from collections import Counter
c = Counter(l)
x = list(c.values())

from math import factorial
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

y = 0
for i in range(len(x)):
    if x[i] != 1:
        y += combinations_count(x[i], 2)

for j in range(n):
    print(y - (c[l[j]] - 1))
### BUGGY CODE ###

from decimal import Decimal
N = int(input())
numlist = [0] * (N + 1)
log2 = [0] * (N + 1)
log5 = [0] * (N + 1)
acc = [[0 for i in range(19)] for j in range(19)]
Ans = 0

for i in range(1,N+1):
  numlist[i] = Decimal(input()) * 1000000000

  wk = numlist[i]
  for cnt in range(1,19):
    if wk % 2 == 0:
      log2[i] += 1
      wk = wk // 2
    else:
      break

  for cnt in range(1,19):
    if wk % 5 == 0:
      log5[i] += 1
      wk = wk // 5
    else:
      break

  acc[log2[i]][log5[i]] += 1
    
for i in range(0,19):
  for j in range(0,19): 
    for k in range(i,19):
      for l in range(0,19):
        if (i + k) >= 18 and (j + l) >= 18 and (i < k or (i == k and j <= l)):
          if acc[i][j] > 0 and acc[k][l] > 0:
            Ans += acc[i][j] * acc[k][l]
            if i >= 9 and j >= 9 and i == k and j == l:
              Ans -= int((acc[i][j] * (acc[i][j] + 1)) / 2)

print(int(Ans))


### FIXED CODE ###

from decimal import Decimal
N = int(input())
#numlist = [0] * (N + 1)
log2 = [0] * (N + 1)
log5 = [0] * (N + 1)
acc = [[0 for i in range(19)] for j in range(19)]
Ans = 0

for i in range(1,N+1):
  #numlist[i] = Decimal(input()) * 1000000000
  wk = Decimal(input())
  wk = int(wk * 1000000000)

  #wk = numlist[i]
  for cnt in range(1,19):
    if wk % 2 == 0:
      log2[i] += 1
      wk = wk // 2
    else:
      break

  for cnt in range(1,19):
    if wk % 5 == 0:
      log5[i] += 1
      wk = wk // 5
    else:
      break

  acc[log2[i]][log5[i]] += 1
    
for i in range(0,19):
  for j in range(0,19): 
    for k in range(i,19):
      for l in range(0,19):
        if (i + k) >= 18 and (j + l) >= 18 and (i < k or (i == k and j <= l)):
          if acc[i][j] > 0 and acc[k][l] > 0:
            Ans += acc[i][j] * acc[k][l]
            if i >= 9 and j >= 9 and i == k and j == l:
              Ans -= int((acc[i][j] * (acc[i][j] + 1)) / 2)

print(int(Ans))
### BUGGY CODE ###

import sys
from itertools import combinations
import bisect
import math
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
l_dict = { i : j for i, j in enumerate(l_ls)}
_sum_ls = []
cnt = 0
for combi in combinations(l_ls, 2):
    bisect.insort_left(_sum_ls, combi[0] + combi[1])
len_sum_ls = len(_sum_ls)
ind = 0
for l in l_ls:
    while ind < len_sum_ls:
        if _sum_ls[ind] <= l:
            ind += 1
        else:
            cnt += ind
            break
print(int(math.factorial(n) / math.factorial(3) / math.factorial(n-3)) - cnt)

### FIXED CODE ###

import sys
from itertools import combinations
import bisect
import math
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
cnt = 0
for a, b in combinations(l_ls, 2):
    _sum = a + b
    ind = bisect.bisect_left(l_ls, _sum)
    cnt += n - ind
print(int(math.factorial(n) // math.factorial(3) // math.factorial(n-3)) - cnt)
### BUGGY CODE ###

import math
# 後で１の位から処理するためにひっくり返しておく
S = list(map(int, reversed(input())))
#print("S = ", S)
"""
「2019の倍数か」は「mod 2019 が 0 になるか」と同意。
しかし、普通に切り出して、１つずつチェックすると計算工数がかかるので、累積和を使う。
各桁の値を （桁の数値a_k）× 10^k と表現し、mod 2019 の値を予め計算し、累積和を作っておく。
ここで、10^k の部分は、2019と互いに疎（公約数がない）なので、
含めて計算しても mod 2019 の周期を乱さない。（勿論オフセットは変わる）
「(i, j) が2019で割り切るか」は、「i～j の累積和が同じ値になる（2019周期）か」と同意。
累積和が同じ値になる個数を数えて、組み合わせを計算すればよい。
"""
# a　：　各桁の mod 2019 値（桁の数値 a_k × 10^k mod 2019）
a = [0 for i in range(len(S))]
# sums ：　累積和
sums = [0 for i in range(len(S) + 1)]
for i in range(len(S)):
    a[i] = (S[i] * 10**i) % 2019
    sums[i + 1] = (sums[i] + a[i]) % 2019
#print("sums = ", sums)
sorts = sorted(sums)
cnt = 0
while len(sorts) > 0:
    picknum = len([i for i in sorts if i == sorts[0]])
    sorts = [i for i in sorts if i != sorts[0]]
    if picknum > 1:
        cnt += math.factorial(picknum) / 2
print(int(cnt))


### FIXED CODE ###

# 後で１の位から処理するためにひっくり返しておく
S = list(map(int, reversed(input())))
#print("S = ", S)
"""
「2019の倍数か」は「mod 2019 が 0 になるか」と同意。
しかし、普通に切り出して、１つずつチェックすると計算工数がかかるので、累積和を使う。
各桁の値を （桁の数値a_k）× 10^k と表現し、mod 2019 の値を予め計算し、累積和を作っておく。
ここで、10^k の部分は、2019と互いに疎（公約数がない）なので、
含めて計算しても mod 2019 の周期を乱さない。（勿論オフセットは変わる）
「(i, j) が2019で割り切るか」は、「i～j の累積和が同じ値になる（2019周期）か」と同意。
累積和が同じ値になる個数を数えて、組み合わせを計算すればよい。
"""
# a　：　各桁の mod 2019 値（桁の数値 a_k × 10^k mod 2019）
a = [0] * len(S)
# sums ：　累積和
sums = [0] * (len(S) + 1)
# d : 10^k
d = 1
# cnt : 累積和 mod 2019 の出現度数表
cnt = [0] * 2019
cnt[0] = 1  # sums[0] = 0 の分
for i in range(len(S)):
    a[i] = (S[i] * d) % 2019
    sums[i + 1] = (sums[i] + a[i]) % 2019
    d = (d * 10) % 2019 
    cnt[sums[i + 1]] += 1
#print("sums = ", sums)
#print("cnt = ", cnt)
ans = 0
for i in cnt:
    ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
P = [-1] + list(map(int,input().split())) + [10**6]
Q = [''.join(map(str,P))]
for i in range(1,n-k+1):
    if (sorted(P[i-1:i+k-1])[1:k] != sorted(P[i:i+k])[0:k-1] or i==1 or i == n-k+1)and P[i:i+k] != sorted(P[i:i+k]):
        q = P[:i] + sorted(P[i:i+k]) + P[i+k:]
        Q += [''.join(map(str,q))]
print(len(Q))


### FIXED CODE ###

class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res

    def add(self, index, x):
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1


N, K = map(int, input().split())
P = list(map(lambda x: int(x) + 1, input().split()))

bit = BinaryIndexedTree(N + 1)
count = 1

for i in range(K):
    bit.add(P[i], 1)

for i in range(N - K):
    mi = bit.bisect_left(1)
    ma = bit.bisect_left(K)
    if P[i] != mi or P[K + i] < ma:
        count += 1
    bit.add(P[i], -1)
    bit.add(P[K + i], 1)

inc = 1
incseq = 0

for i in range(N - 1):
    if P[i] < P[i + 1]:
        inc += 1
        if inc == K:
            incseq += 1
    else:
        inc = 1

print(count - max(0, incseq - 1))
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = [0] * n
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2, n):
    ik = max(0, i-k)
    dp[i] = np.min(dp[ik:i]+np.abs(h[i]-h[ik:i]))

print(int(dp[n-1]))


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
h = np.array([int(i) for i in input().split()])

dp = np.zeros(n)
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2, n):
    ik = max(0, i-k)
    dp[i] = np.min(dp[ik:i]+np.abs(h[i]-h[ik:i]))

print(int(dp[n-1]))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
judge = True
ans = 1
for i in a:
    ans *= i
    if (ans > 1000000000000000000):
        judge = False

if judge:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
judge = True
ans = 1
for i in a:
    ans *= i
    if (ans > 1000000000000000000):
        judge = False
        break

if judge:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import math as m

a, b, x = map(int, input().split())

x = float(x)
d_max = float(90)
d_min = float(0)
res = float(100)

if x >= a**2*b:
    print(0)
    exit()

while res > 10e-8:
    d_mid = (d_max+d_min)/2
    l1 = a*m.tan(d_mid/180*m.pi)
    if l1-b > 0:
        l2 = (l1-b)*m.tan((90-d_mid)/180*m.pi)
    else:
        l2 = 0
    v = a*(a*b - 1/2*a*l1 + 1/2*(l1-b)*l2)
    res = abs(x-v)
    if x - v < 0:
        d_min = d_mid
    else:
        d_max = d_mid
print(d_mid)

### FIXED CODE ###

import math as m

def vol(a,b,x,d):
    if a**2*b / 2 < x:
        return a**2*b - 1/2*a**3 * m.tan(m.radians(d))
    else:
        return 1/2*a*b**2 * m.tan(m.radians(90-d))

a, b, x = map(int, input().split())

if a**2*b == x:
    print(0)
    exit()

res = x
d_max = 90
d_min = 0
while res > 10e-8:
    d = (d_max+d_min)/2
    if vol(a,b,x,d) - x > 0:
        d_min = d
    else:
        d_max = d
    res = abs(x - vol(a,b,x,d))

print(d)
### BUGGY CODE ###

from functools import reduce
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
 
answer = sum(lcm//x for x in A)
answer %= MOD
print(answer)

### FIXED CODE ###

from functools import reduce
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
lcm %= MOD

coef = sum(pow(a, MOD-2, MOD) for a in A)
ans = lcm * coef % MOD

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

S = input()
l = [0]
r = [0]
c = 0
for i in range(len(S)):
    if S[i] == '<':
        c += 1
    else:
        c = 0
    l.append(c)
c = 0
for i in range(len(S)-1,-1,-1):
    if S[i] == '>':
        c += 1
    else:
        c = 0
    r.insert(0, c)
print(sum([max(l[i],r[i]) for i in range(len(S)+1)]))


### FIXED CODE ###

S = input()
l = [0] * (len(S)+1)
r = [0] * (len(S)+1)
for i in range(len(S)):
    if S[i] == '<':
        l[i+1] = l[i] + 1
for i in range(len(S)-1,-1,-1):
    if S[i] == '>':
        r[i] = r[i+1] + 1
print(sum([max(l[i],r[i]) for i in range(len(S)+1)]))
### BUGGY CODE ###

import sys

x = int(input())
nums = [i for i in range(1, 100004, 2)]
del nums[0]
if x == 2:
    print(2)
    sys.exit()
while nums:
    primal = nums.pop(0)
    if primal >= x:
        print(primal)
        break
    nums = [num for num in nums if num % primal != 0]


### FIXED CODE ###

import sys

x = int(input())
nums = [i for i in range(1, 100004, 2)]
del nums[0]
if x == 2:
    print(2)
    sys.exit()
while nums:
    primal = nums.pop(0)
    if primal >= x:
        print(primal)
        break
    nums = [num for num in nums if num % primal != 0]
### BUGGY CODE ###

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

cnt = 0
for i in range(n//r + 1):
    for j in range(n//g + 1):
        k = (n - i*r - j*g)
        if k >= 0 and k % b == 0:
            cnt += 1
            # print(i, j, k)

print(cnt)

### FIXED CODE ###

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

cnt = 0
for i in range(n//r + 1):
    for j in range(n//g + 1):
        k = (n - i*r - j*g)
        if k >= 0 and k % b == 0:
            cnt += 1
            # print(i, j, k)

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

import sys
input = sys.stdin.readline


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def main():
    N, K = map(int, input().split())
    ac = [0] * (N + 1)
    eps = 10 ** -6
    place = {0: 0}
    for i in range(N):
        a = int(input()) - K
        ac[i+1] = ac[i] + a + eps
        place[ac[i+1]] = i+1
    ac.sort()
    ac_cmpr = [0] * (N+1)
    for i in range(N+1):
        ac_cmpr[place[ac[i]]] = i + 1
    bit = Bit(N+2)
    bit.add(ac_cmpr[0], 1)
    ans = 0
    for i in range(1, N+1):
        ans += bit.sum(ac_cmpr[i])
        bit.add(ac_cmpr[i], 1)

    print(ans)


if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def main():
    N, K = map(int, input().split())
    ac = [0] * (N + 1)
    place = {0: 0}
    for i in range(N):
        a = int(input()) - K
        ac[i+1] = ac[i] + a * (10 ** 5) + 1
        place[ac[i+1]] = i+1
    ac.sort()
    ac_cmpr = [0] * (N+1)
    for i in range(N+1):
        ac_cmpr[place[ac[i]]] = i + 1
    bit = Bit(N+2)
    bit.add(ac_cmpr[0], 1)
    ans = 0
    for i in range(1, N+1):
        ans += bit.sum(ac_cmpr[i])
        bit.add(ac_cmpr[i], 1)

    print(ans)


if __name__=='__main__':
    main()