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

def flpl(): return [float(i) for i in input().split()]
def inpl(): return [int(i) for i in input().split()]
import numpy as np
xs, ys, xt, yt = flpl()
rs,rt = 0, 0
N = int(input())
xyr = [(xs, ys, rs),(xt, yt,rt)] + [inpl() for _ in range(N)]
X, Y, R = np.array(xyr).T
X, Y, R = np.tile(X, (N+2, 1)), np.tile(Y, (N+2, 1)), np.tile(R, (N+2, 1))
edge = np.maximum(np.zeros((N+2, N+2)), np.sqrt(np.square(X-X.T) +\
                    np.square(Y-Y.T))-(R+R.T))
inf = float('inf')
dist = np.array([inf for _ in range(N+2)])
dist[0] = 0 
import heapq

remain = set(range(N+2))
Q = []
heapq.heappush(Q,(0,0))
while Q:
    k = heapq.heappop(Q)
    k = k[1]
    if k not in remain:
        continue
    remain.remove(k)
    for j in remain:
        if dist[k] + edge[k][j] < dist[j]:
            dist[j] = dist[k] + edge[k][j] 
            heapq.heappush(Q,(dist[j],j)) 
print(dist[1])

### FIXED CODE ###

def flpl(): return [float(i) for i in input().split()]
def inpl(): return [int(i) for i in input().split()]
import heapq
def dijkstra(vnum, vs):
    dist = [float('inf') for _ in range(vnum)]
    dist[vs] = 0 
    remain = set(range(vnum))
    Q = []
    heapq.heappush(Q,(0,vs))
    while Q:
        c, vn = heapq.heappop(Q)
        if vn not in remain :
            continue
        remain.remove(vn)
        for j in remain:
            evnj = edge(vn, j)
            if dist[vn] + evnj < dist[j]:
                dist[j] = dist[vn] + evnj 
                heapq.heappush(Q,(dist[j],j)) 
        if not remain:
            break
    return dist
def edge(s, t):
    return max(((X[s] - X[t])**2 + (Y[s] - Y[t])**2)**(1/2) -(R[s]+R[t]), 0)

xs, ys, xt, yt = flpl()
N = int(input())
xyr = [(xs, ys, 0),(xt, yt, 0)] + [inpl() for _ in range(N)]
X, Y, R = list(map(list, zip(*xyr)))
D = dijkstra(N+2, 0)
print(D[1])
### BUGGY CODE ###

import sys
from collections import defaultdict


N = int(input())
P = tuple(map(int, input().split()))

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]
    checked = defaultdict(lambda: 0)

    while queue:
        qsn = queue.pop()

        if checked[qsn]: continue

        checked[qsn] = 1
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)


### FIXED CODE ###

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

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
b = [list(map(int, input().split())) for _ in range(h)]

dp = [[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(abs(b[0][0] - a[0][0]))
for i in range(h):
    for j in range(w):
        t = abs(b[i][j] - a[i][j])
        if i > 0:
            for x in dp[i-1][j]:
                dp[i][j].add(abs(x + t))
                dp[i][j].add(abs(x - t))
        if j > 0:
            for x in dp[i][j-1]:
                dp[i][j].add(abs(x + t))
                dp[i][j].add(abs(x - t))

#print(dp)
ans = sorted(list(dp[h-1][w-1]))
print(ans[0])


### FIXED CODE ###

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
b = [list(map(int, input().split())) for _ in range(h)]
ab = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        ab[i][j] = abs(a[i][j] - b[i][j])

m = 12800
dp = [[0] * w for _ in range(h)]
dp[0][0] = (1 << (m + ab[0][0])) | (1 << (m - ab[0][0]))
for i in range(h):
    for j in range(w):
        for dx, dy in [(1, 0), (0, 1)]:
            nx, ny = i + dx, j + dy
            if 0 <= nx < h and 0 <= ny < w:
                dp[nx][ny] = dp[nx][ny] | (dp[i][j] << ab[nx][ny])
                dp[nx][ny] = dp[nx][ny] | (dp[i][j] >> ab[nx][ny])

#print(dp[-1][-1])
for i in range(m+1):
    if (dp[h-1][w-1] >> i) & 1:
        ans = m - i

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

N=int(input())
from collections import defaultdict
import math
def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]
def search_divisor_num_1(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num
ans=0
for i in range(1,N+1):
  ans+=search_divisor_num_1(i)*i
print(ans)

### FIXED CODE ###

N=int(input())
sum=[0]*(N+3)
ans=0
for i in range(1,N+1):
  sum[i]=sum[i-1]+i
for i in range(1,N+1):
  tmpn=N//i
  tmpsum = sum[tmpn]
  ans+=tmpsum*i
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = set()
for i in range(k):
    a, b = map(int, input().split())
    s.update(range(a, b + 1))
s = sorted(list(s))

dp = [0] + [0] * n
dp[1] = 1
for i in range(1, n + 1):
    for j in s:
        if i + j > n:
            break
        else:
            dp[i + j] = (dp[i + j] + dp[i]) % MOD
print(dp[n])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = list()
for i in range(k):
    s.append(tuple(map(int, input().split())))

dp = [0] + [0] * n
diff = [0] + [0] * n
dp[1] = 1
for i in range(1, n):
    for j, k in s:
        if i + j > n:
            continue
        diff[i + j] += dp[i]
        if i + k + 1 > n:
            continue
        diff[i + k + 1] -= dp[i]
    dp[i] = (dp[i - 1] + diff[i]) % MOD
    dp[i + 1] = (dp[i] + diff[i + 1]) % MOD
print(dp[n])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = input()

    ans = 0
    for p in range(1000):
        p = str(p).zfill(3)

        i = 0
        for j in range(N):
            if S[j] == p[i]:
                i += 1

            if i == 3:
                ans += 1
                break

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = list(input())
    ans = 0

    for p in range(1000):
        p = str(p).zfill(3)
        i = 0
        for j in range(N):
            if p[i] == S[j]:
                i += 1
            if i == 3:
                ans += 1
                break

    print(ans)


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

n, m = map(int, input().split())
mod = 10 ** 9 + 7

fac = [1 for _ in range(m+1)]
for i in range(m):
    fac[i+1] = fac[i] * (i+1) % mod
memo = [[-1 for _ in range(m+1)] for _ in range(n+1)]
for i in range(m+1):
    memo[1][i] = i-1

def g(n, m):
    if memo[n][m] != -1:
        return memo[n][m]
    
    memo[n][m] = (g(n-1, m-1) * n + fac[n-1] * (n-1)) % mod
    return memo[n][m]

ans = g(n, m)

tmp = m
for _ in range(n):
    ans *= tmp
    ans %= mod
    tmp -= 1

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
mod = 10 ** 9 + 7

f = [1, 1]
f_inv = [1, 1]
inv = [0, 1]
 
for i in range(2, m+1):
    f.append((f[-1] * i ) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    f_inv.append((f_inv[-1] * inv[-1]) % mod)

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod

def per(n, k):
    return f[n] * f_inv[n-k] % mod

ans = 0
for i in range(0, n+1):
    res = comb(n, i) *  per(m, i) * (per(m-i, n-i) ** 2)
    if i % 2 == 1:
        res *= -1
    ans += res
    ans %= mod

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

# -*- coding utf-8 -*-
from collections import defaultdict

MOD = 10 ** 9 + 7
N, Q = map(int, input().split())

tree = defaultdict(set)
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)

counter = defaultdict(int)
for i in range(Q):
    p, x = map(int, input().split())
    counter[p] += x

cur_node = set()
cur_node.add(1)
pre_node = set()
while len(cur_node) != 0:
    next_node = set()
    for ni in cur_node:
        for nj in tree[ni]:
            if nj in pre_node:
                continue
            counter[nj] += counter[ni]
            next_node.add(nj)
    pre_node = cur_node
    cur_node = next_node

print(' '.join((str(counter[i]) for i in range(1, N + 1))))


### FIXED CODE ###

# -*- coding utf-8 -*-
from collections import defaultdict

MOD = 10 ** 9 + 7
N, Q = map(int, input().split())

tree = defaultdict(set)
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)

counter = defaultdict(int)
for i in range(Q):
    p, x = map(int, input().split())
    counter[p] += x

cur_node = set()
cur_node.add(1)
pre_node = set()
while len(cur_node) != 0:
    next_node = set()
    for ni in cur_node:
        for nj in tree[ni]:
            if {nj} <= pre_node:
                continue
            counter[nj] += counter[ni]
            next_node.add(nj)
    pre_node = cur_node
    cur_node = next_node

print(' '.join((str(counter[i]) for i in range(1, N + 1))))
### BUGGY CODE ###

# ダブリング
 
N,K = map(int,input().split())
A = [-1] + list(map(int,input().split()))
 
D = 60
 
to = [[-1 for i in range(N+1)] for j in range(D)]
to[0] = A
 
for i in range(1,D):
    for j in range(1,N+1):
        to[i][j] = to[i-1][to[i-1][j]]
 
ans = 1
for i in range(D):
    if K>>i&1:
        ans = to[i][ans]
 
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = [-1] + list(map(int,input().split()))

visit = [False for i in range(N+1)]
now = 1
cnt = 0
while True:
    if visit[now]:
        break
    visit[now] = True
    now = A[now]
    cnt += 1
cnt2 = 0
visit2 = [False for i in range(N+1)]
while True:
    if visit2[now]:
        break
    visit2[now] = True
    now = A[now]
    cnt2 += 1

if cnt >= K:
    ans = 1
    for i in range(K):
        ans = A[ans]

else:
    K -= cnt
    K = K%cnt2
    ans = now
    for i in range(K):
        ans = A[ans]
print(ans)
### BUGGY CODE ###

n = int(input())
list_s = [''.join(sorted(input())) for _ in range(n)]
res = 0
for i in range(n):
    for j in range(i + 1, n):
        if list_s[i] == list_s[j]:
            res += 1
print(res)

### FIXED CODE ###

import collections

n = int(input())

counter = collections.Counter()
for _ in range(n):
    s = ''.join(sorted(input()))
    counter[s] += 1

res = 0
for value in counter.values():
    if value > 1:
        res += value * (value - 1) // 2

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

def cal(a):
    cal_sum = 0
    for i in range(1, a + 1):
        cal_sum += i
    return (cal_sum / a)

N, K = map(int, input().split())
p = list(map(int, input().split()))
ans_raw = []

for i in range(0, N):
    p[i] = cal(p[i])

for i in range(0, N - K + 1):
    ans = 0
    for j in range(i, i + K):
        ans += p[j]
    ans_raw.append(ans)


print(max(ans_raw))

### FIXED CODE ###

def cal(a):
 	return ((1 + a) / 2)
 
N, K = map(int, input().split())
p = list(map(int, input().split()))
ans_raw = []
sum_raw = []
sum_cal = 0
 
for i in range(0, N):
    p[i] = cal(p[i])


for i in range(0, N):
	sum_cal += p[i]
	sum_raw.append(sum_cal)

for i in range(0, N - K):
	ans = sum_raw[i + K] - sum_raw[i]
	ans_raw.append(ans)

ans_0 = sum_raw[K - 1]
ans_raw.append(ans_0)

print(max(ans_raw))
### BUGGY CODE ###

l = list(input())
op = 0
while True:
    ss = None
    s_p = l[0]
    for i, s in enumerate(l[1:], start=1):
        if s == s_p:
            continue
        else:
            for i, m in enumerate(l[:i]):
                l[i] = s
            ss = s
            op += 1
            break
    if ss is None:
        break
    else:
        l.insert(0, ss)

print(op)


### FIXED CODE ###

l = list(input())
op = 0
s_p = l[0]
for i, s in enumerate(l[1:], start=1):
    if s == s_p:
        continue
    else:
        s_p = s
        op += 1
print(op)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = n
for i in range(n):
    for j in range(i+1):
        if p[i]>p[j]:
            ans -=1
            break
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0
m = 200001
for i in p:
    if i<m:
        ans+=1
        m=i
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
cost=[0,abs(h[1]-h[0])]

for i in range(2,N):
    cand=10**10
    for j in range(K):
        if j==i:
            break
        cand=min(cand,cost[i-j-1]+abs(h[i]-h[i-j-1]))
    cost.append(cand)

print(cost[-1])

### FIXED CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
cost=[0,abs(h[1]-h[0])]

for i in range(2,N):
    cand=10**10
    for j in range(K):
        if j==i:
            break
        cand=min(cand,cost[i-j-1]+abs(h[i]-h[i-j-1]))
    cost.append(cand)

print(cost[-1])
### BUGGY CODE ###

N,M = map(int,input().split())
a = [int(input()) for m in range(M)]
ans = []
P = 10**9+7
for n in range(N):
    if n+1 in a:
        ans.append(0)
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])


### FIXED CODE ###

from collections import deque
N,M = map(int,input().split())
a = deque([int(input()) for m in range(M)]+[-1])
ans = []
P = 10**9+7
for n in range(N):
    if n+1 == a[0]:
        ans.append(0)
        a.popleft()
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])
### BUGGY CODE ###

s=input()[::-1]
if s[0]=="?":
    p=[1]*10+[0]*3
else:
    p=[0]*13
    p[int(s[0])]=1
q=10
for i in s[1:]:
    if i!="?":
        i=int(i)
        s=q*i%13
        p=p[-s:]+p[:-s]
    else:
        d=[0]*13
        for j in range(10):
            s=q*j%13
            r=p[-s:]+p[:-s]
            d=[(r[i]+d[i])%(10**9+7)for i in range(13)]
        p=d
    q=(q*10)%13
print(p[5]%(10**9+7))

### FIXED CODE ###

s=input()[::-1]
p=[1]+[0]*12
q=1
t=[[(i*k)%13 for i in range(10)]for k in range(13)]
for i in s:
    if i!="?":
        i=int(i)
        g=t[q][i]
        p=p[-g:]+p[:-g]
    else:
        d=[0]*13
        for j in t[q]:
            r=p[-j:]+p[:-j]
            d=[(r[i]+d[i])%(10**9+7)for i in range(13)]
        p=d
    q=(q*10)%13
print(p[5]%(10**9+7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import copy
from collections import deque

class SegTree():
    def __init__(self, n):
        self.value = [0 for i in range(n*2)]

MOD = 10 ** 9 + 7

def getinvmod(n):
    return [pow(i, MOD-2, MOD) for i in range(n+1)]

def judge(monsterss, n_attack, a, b):
    monsters = copy.copy(monsterss)
    attack = 0
    for monster in monsters:
        # monster -= n_attack * b
        if monster > 0:
            attack += math.ceil(max(0, (monster - b*n_attack)/(a-b)))

    return attack <= n_attack


def main():
    n, a, b = getList()
    monsters = []
    for i in range(n):
        monsters.append(getN())

    mn = 0
    mx = 10 ** 15
    while(mx - mn > 1):
        mid = (mn + mx) // 2
        if judge(monsters, mid, a, b):
            mx = mid
        else:
            mn = mid

    if judge(monsters, mn, a, b):
        print(mn)
    else:
        print(mx)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import copy
from collections import deque

class SegTree():
    def __init__(self, n):
        self.value = [0 for i in range(n*2)]

MOD = 10 ** 9 + 7

def getinvmod(n):
    return [pow(i, MOD-2, MOD) for i in range(n+1)]

def judge(monsters, n_attack, a, b):
    attack = 0
    for monster in monsters:
        # monster -= n_attack * b
        if monster > 0:
            attack += math.ceil(max(0, (monster - b*n_attack)/(a-b)))

    return attack <= n_attack


def main():
    n, a, b = getList()
    monsters = []
    for i in range(n):
        monsters.append(getN())

    mn = 0
    mx = 10 ** 15
    while(mx - mn > 1):
        mid = (mn + mx) // 2
        if judge(monsters, mid, a, b):
            mx = mid
        else:
            mn = mid
        # print(monsters)

    if judge(monsters, mn, a, b):
        print(mn)
    else:
        print(mx)



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

import sys,queue,math,copy,itertools,bisect,collections
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
dp = [[0] * 13 for _ in range(len(S)+1)]
dp[0][0] = 1

def add_dp(i,j):
    for k in range(13):
        l = (k * 10 + j) % 13
        dp[i][l] += dp[i-1][k]

for i in range(1,len(S)+1):
    x = S[i-1]
    if x == '?':
        for j in range(10):
            add_dp(i,j)
    else:
        add_dp(i,int(x))
    for j in range(13):
        dp[i][j] %= MOD

print (dp[-1][5])


### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections
MOD = 10**9 + 7
S = sys.stdin.readline().rstrip()
dp = [[0] * 13 for _ in range(len(S)+1)]
dp[0][0] = 1

for i in range(1,len(S)+1):
    x = S[i-1]
    if x == '?':
        for j in range(10):
            for k in range(13):
                dp[i][(k * 10 + j) % 13] += dp[i - 1][k]
    else:
        for k in range(13):
            dp[i][(k * 10 + int(x)) % 13] += dp[i - 1][k]
    for j in range(13):
        dp[i][j] %= MOD

print (dp[-1][5])
### BUGGY CODE ###

n = input()
s = input()

n = int(n)

allnum = set(range(0, 1000))
ans = []
counts = 0



for i in range(n - 2):
    checked_j = []
    for j in range(i + 1, n - 1):
        if j in checked_j:
            continue
        else:
            checked_j.append(j)
        # checked_j.append(j)

        num = int(s[i]) * 100 + int(s[j]) * 10

        if num in ans:
            continue
        else:
            ans.append(num)

            saigo_cnt = len(set([int(s[k]) for k in range(j + 1, n)]))
            counts += saigo_cnt

print(counts)


### FIXED CODE ###

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

ans_count =0

for i in range(10):
    for j in range(10):
        for k in range(10):
            i_pos = s.find(str(i))

            if i_pos < 0:
                continue

            j_pos = s.find(str(j),i_pos+1)

            if j_pos < 0:
                continue

            k_pos = s.find(str(k), j_pos +1)

            if k_pos < 0:
                continue

            ans_count += 1

print(ans_count)
### BUGGY CODE ###

S=input()
T=len(S)
a=0
mod=[0]*2019
mod[0]+=1
for i in range(T):
 a+=(int(S[T-i-1])*(10**i))%2019
 b=a%2019
 mod[b]+=1
c=0
for i in range(2019):
 if mod[i]>=2:
  c+= mod[i]*(mod[i]-1)/2
print(int(c))


### FIXED CODE ###

S=input()
T=len(S)
a=0
d=1
mod=[0]*2019
mod[0]+=1
for i in range(T):
 a+=(int(S[T-i-1])*(d))%2019
 b=a%2019
 mod[b]+=1
 d*=10
 d%=2019
c=0
for i in range(2019):
 if mod[i]>=2:
  c+= mod[i]*(mod[i]-1)/2
print(int(c))
### BUGGY CODE ###

N, M = map(int, input().split())
from_1 = []
to_N = []

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from_1.append(b)
    elif b == N:
        to_N.append(a)
        
from_1.sort()
to_N.sort()
flg = 0

for i in range(len(from_1)):
    if from_1[i] in to_N:
        flg = 1
        break
        
if flg:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

N, M = map(int, input().split())
lst = []

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        lst.append(b)
    elif b == N:
        lst.append(a)
        
lst.sort()
flg = 0

for i in range(len(lst) - 1):
    if lst[i] == lst[i + 1]:
        flg = 1
        break
        
if flg:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.Counter()
    ans = 0
    S = [SI() for _ in range(N)]
    C = []
    for s in S:
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),-1,-1):
            if i == len(s):
                c = 0
            else:
                c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
            if i > 0:
                d = c * 27
                for j in range(26):
                    if a[i-1] & (1<<j):
                        cnt[(d+j+1)%MOD] += 1
        C.append(c)
    for c in C:
        ans += cnt[c] - 1

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

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.defaultdict(int)
    ans = 0
    S = [SI() for _ in range(N)]
    for s in S:
        h = 0
        for i in range(len(s)-1,0,-1):
            h = (h * 27 + ord(s[i]) - ord('a') + 1) % MOD
        cnt[h] |= 1<<(ord(s[0])-ord('a'))

    for s in S:
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        h = 0
        for i in range(len(s)-1,0,-1):
            ans += bin(cnt[h] & a[i]).count('1')
            h = (h * 27 + ord(s[i]) - ord('a') + 1) % MOD

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

from fractions import gcd
import math
n = int(input())
a = list(map(int, input().split()))
def lcm(a, b):
    return (a * b) // gcd(a, b)
m = 1
for x in a:
    m = lcm(m, x)
# print(m)
MOD = 1000000007
ans = 0
for x in a:
    b = m // x
    ans = (ans + b) % MOD
print(math.floor(ans))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from fractions import gcd
import math
n = int(input())
a = list(map(int, input().split()))
def lcm(a, b):
    return (a * b) // gcd(a, b)
m = 1
for x in a:
    m = (m * x) // gcd(m, x)
# print(m)
MOD = 1000000007
ans = 0
for x in a:
    b = m // x
    ans = ans + b
ans = ans % MOD
print(math.floor(ans))