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

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

import re

n = ni()
s = ns()
cnt = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            pattern = ".*" + str(i) + ".*" + str(j) + ".*" + str(k) + ".*"
            reptn = re.compile(pattern)
            if re.search(reptn, s):
                cnt += 1

print(cnt)


### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

import re

n = ni()
s = ns()
cnt = 0
cand = []
for i in range(10):
    for j in range(10):
        for k in range(10):
            stri = str(i)
            strj = str(j)
            strk = str(k)
            first = False
            second = False
            for si in s:
                if si == strk and first and second:
                    cnt += 1
                    break
                elif si == strj and first:
                    second = True
                elif si == stri:
                    first = True

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

def main():
    s = input()
    n = len(s)
    modlis = [0 for i in range(2019)]
    modlis[0]=1
    t = 0
    for i in range(n):
        t = int(s[n-1-i:])%2019
        modlis[t]+=1

    ans = 0
    for i in range(2019):
        ans += (modlis[i]*(modlis[i]-1))//2
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input()
    n = len(s)
    modlis = [0 for i in range(2019)]
    modlis[0]=1
    t = 0
    m = 1
    for i in range(n):
        t = (t+int(s[n-1-i])*m)%2019
        m = m*10%2019
        modlis[t]+=1

    ans = 0
    for i in range(2019):
        ans += (modlis[i]*(modlis[i]-1))//2
    print(ans)


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

N, K = list(map(int, input().split()))
tree = []
for i in range(N):
    tree.append(int(input()))

tree.sort()
m = float("inf")
for i in range(N-K+1):
    d = tree[i:i+K]
    dif = max(d) - min(d)
    m = dif if m > dif else m

print(int(m))



### FIXED CODE ###

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

t.sort()
m = 10 ** 9
for i in range(N-K+1):
    m = min(t[i+K-1] - t[i], m)

print(int(m))
### BUGGY CODE ###

import fractions
import functools

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

gcdlist = []

def gcdpy(numbers):
	return functools.reduce(fractions.gcd, numbers)

for i in range(0,N):
	I = A[i]
	A[i] = A[i-1]
	gcdlist.append(gcdpy(A))
	A[i] = I
	
print(max(gcdlist))

### FIXED CODE ###

#最大公約数を求める関数を再帰的に定義
def gcd(x,y):
	if x < y:
		x,y = y,x
	if y == 0:
		return x
	#一方が0の時、他方を最大公約数として定義
	return gcd(y,x % y)
	
N = int(input())
A = list(map(int,input().split()))

L = [0]
R = [0]
gcdlist = []

#リストの前と後ろから値を取得し
#A[i]を除いてA[i]以前と以降の最大公約数を算出
for i in range(N):
	L.append(gcd(L[i],A[i]))
	R.append(gcd(R[i],A[N-i-1]))


#i毎にA[i]を除いた最大公約数のリストを作成
for i in range(N):
	gcdlist.append(gcd(L[i],R[N-i-1]))

print(max(gcdlist))
### BUGGY CODE ###

import sys
f = sys.stdin

def mix(a,b):
    return (min(a[0],b[0]),min(a[1],b[1]),max(a[2],b[2]),max(a[3],b[3]))

s = {}

n, d = map(int, f.readline().split())
for _ in range(n):
    x, y, b = map(int, f.readline().split())
    s[b] = mix(s[b],(x,y,x,y)) if b in s else (x,y,x,y)

max_size = 0
b = sorted(s.keys())
for i in range(len(b)):
    xy = s[b[i]]
    for j in range(i + 1,len(b)):
        if b[i] + d < b[j]:
            break
        xy = mix(xy,s[b[j]])
    max_size = max(max_size,((xy[2] - xy[0]) * (xy[3] - xy[1])))
print(max_size)

### FIXED CODE ###

import math
def segmentTree(dat, f, sentinel):
        pad = 2 ** math.ceil(math.log(len(dat),2))
        dat = [0] * pad + dat + [sentinel] * (pad - len(dat))
        for i in range(pad - 1, 0, -1):
            dat[i] = f(dat[i * 2],dat[i * 2 + 1])
        return dat

def get_lr(b,d):
    l = r = 0
    while r < len(b):
        while b[l] + d < b[r]:
            l += 1
        for r in range(r,len(b)):
            if b[l] + d < b[r]:
                r -= 1
                break
        r += 1
        yield l,r
        l += 1
    
import sys
f = sys.stdin

_, d = map(int, f.readline().split())

xyb = []
for line in f:
    xyb.append(tuple(map(int, line.split())))
from operator import itemgetter
xyb.sort(key=itemgetter(2))

x = [xybi[0] for xybi in xyb]
y = [xybi[1] for xybi in xyb]
b = [xybi[2] for xybi in xyb]

xmax = segmentTree(x,max,sentinel = 0)
xmin = segmentTree(x,min,sentinel = 2000000)
ymax = segmentTree(y,max,sentinel = 0)
ymin = segmentTree(y,min,sentinel = 2000000)


pad = len(xmax) // 2
max_size = 0
def create_index(l,r):
    index = []
    ia = index.append
    while l < r:
        if r & 1:
            r -= 1
            ia(r)
        if l & 1:
            ia(l)
            l += 1
        l >>= 1
        r >>= 1
    return index

for l,r in get_lr(b,d):
    l += pad 
    r += pad
    index = create_index(l,r)

    now_xmax = max(xmax[i] for i in index)
    now_ymax = max(ymax[i] for i in index)
    if max_size < now_xmax * now_ymax:
        max_size = max(max_size,((now_xmax - min(xmin[i] for i in index)) * (now_ymax - min(ymin[i] for i in index))))
print(max_size)
### BUGGY CODE ###

n, m = map(int, input().split())
broken = [int(input()) for _ in range(m)]
f = [1, 1]

for i in range(2, n+1):
  f_nm1 = f[i-1] if i-1 not in broken else 0
  f_nm2 = f[i-2] if i-2 not in broken else 0
  f.append(f_nm1 + f_nm2)

print(f[-1]%1000000007)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
state = [1] * (n+1)

for _ in range(m):
  state[int(input())] = 0
  
f = [1, 1]

for i in range(2, n+1):
  f_nm1 = f[i-1] if state[i-1]==1 else 0
  f_nm2 = f[i-2] if state[i-2]==1 else 0
  f.append(f_nm1 + f_nm2)

print(f[-1]%1000000007)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
x = 1
for num in a:
    x *= num
if x > 10**18:
    print('-1')
else:
    print(x)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
x = 1
for num in a:
    x *= num
    if x > 10**18:
        x = -1
        break
if 0 in a:
    x = 0
print(x)
### BUGGY CODE ###

n=int(input())
s=[input() for i in range(n)]
a=set(s)
ss=sorted(list(a))
ct=0
for i in a:
    if ct < s.count(i):
        ct = s.count(i)

for i in ss:
    if ct == s.count(i):
        print(i)


### FIXED CODE ###

import sys
n=int(input())
s=sorted([input() for i in range(n)])
ct=0
tmp=1
for i in range(n-1):
    if s[i] ==s[i+1]:
        tmp+=1
    else:
        if tmp>ct:
            ct=tmp
        tmp=1
if tmp > ct:
    ct = tmp
    
if tmp == 1:
    for i in range(n):
        print(s[i])
    sys.exit()

tmp=1
for i in range(n-1):
    if s[i] ==s[i+1]:
        tmp+=1
        if tmp == ct:
            print(s[i])
    else:
        tmp=1
### BUGGY CODE ###

import sys


n=int(input())
D=list(map(int,input().split()))
M=int(input())
T=list(map(int,input().split()))
for i in T:
    if(i not in D):
        print("NO")
        sys.exit()
    else:
        D.remove(i)
print("YES")

### FIXED CODE ###

import sys
from collections import Counter


n=int(input())
Dc=Counter(input().split())
m=int(input())
Tc=Counter(input().split())
for key,val in Tc.items():
    if(val>Dc[key]):
        print("NO")
        sys.exit()
print("YES")
### BUGGY CODE ###

n,m=map(int,input().split())
for i in range(n,m+1):
  if m%i==0:
    print(m//i)
    exit()
    

### FIXED CODE ###

n,m=map(int,input().split())
for i in range(n,10**8):
  if m%i==0:
    print(m//i)
    exit()
print(1)
### BUGGY CODE ###

def main():
    n = int(input())
    print(sum(range(n)))


main()


### FIXED CODE ###

def main():
    n = int(input())
    print((n - 1) * n // 2)


main()
### BUGGY CODE ###

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

grid = []

for i in range(H):
    s = input()
    r = []
    for j, x in enumerate(s):
        r.append(x)

    grid.append(r)


H_cnt = [[0] * W for _ in range(H)]
W_cnt = [[0] * W for _ in range(H)]

for r in range(H):
    idx = 0

    while idx < W:
        if grid[r][idx] == '.' and (idx == 0 or grid[r][idx - 1] == '#'):
            cnt = 1
            st = idx
            if idx == W - 1 or grid[r][idx + 1] == '#':
                W_cnt[r][idx] = 1
        elif grid[r][idx] == '.' and (idx == W - 1 or grid[r][idx + 1] == '#'):
            cnt += 1
            for i in range(st, idx + 1):
                W_cnt[r][i] = cnt
        elif grid[r][idx] == '.':
            cnt += 1
        elif grid[r][idx] == '#':
            pass

        idx += 1

for c in range(W):
    idx = 0

    while idx < H:
        if grid[idx][c] == '.' and (idx == 0 or grid[idx - 1][c] == '#'):
            cnt = 1
            st = idx
            if idx == H - 1 or grid[idx + 1][c] == '#':
                H_cnt[idx][c] = 1
        elif grid[idx][c] == '.' and (idx == H - 1 or grid[idx + 1][c] == '#'):
            cnt += 1
            for i in range(st, idx + 1):
                H_cnt[i][c] = cnt
        elif grid[idx][c] == '.':
            cnt += 1
        elif grid[idx][c] == '#':
            pass

        idx += 1

max_ = 0
for r in range(H):
    for c in range(W):
        max_ = max(max_, W_cnt[r][c] + H_cnt[r][c] - 1)

print(max_)


### FIXED CODE ###

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

grid = []

for i in range(H):
    s = input()
    r = []
    for j, x in enumerate(s):
        r.append(x)

    grid.append(r)


H_cnt = [[0] * W for _ in range(H)]
W_cnt = [[0] * W for _ in range(H)]

for r in range(H):
    idx = 0

    while idx < W:
        if grid[r][idx] == '.' and (idx == 0 or grid[r][idx - 1] == '#'):
            cnt = 1
            st = idx
            if idx == W - 1 or grid[r][idx + 1] == '#':
                W_cnt[r][idx] = 1
        elif grid[r][idx] == '.' and (idx == W - 1 or grid[r][idx + 1] == '#'):
            cnt += 1
            for i in range(st, idx + 1):
                W_cnt[r][i] = cnt
        elif grid[r][idx] == '.':
            cnt += 1
        elif grid[r][idx] == '#':
            pass

        idx += 1

for c in range(W):
    idx = 0

    while idx < H:
        if grid[idx][c] == '.' and (idx == 0 or grid[idx - 1][c] == '#'):
            cnt = 1
            st = idx
            if idx == H - 1 or grid[idx + 1][c] == '#':
                H_cnt[idx][c] = 1
        elif grid[idx][c] == '.' and (idx == H - 1 or grid[idx + 1][c] == '#'):
            cnt += 1
            for i in range(st, idx + 1):
                H_cnt[i][c] = cnt
        elif grid[idx][c] == '.':
            cnt += 1
        elif grid[idx][c] == '#':
            pass

        idx += 1

max_ = 0
for r in range(H):
    for c in range(W):
        max_ = max(max_, W_cnt[r][c] + H_cnt[r][c] - 1)

print(max_)
### BUGGY CODE ###

import fractions

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

if Ai == [Ai[0]] * len(Ai):
    print(Ai[0])
    quit()

Ai.sort()

i = 1
diff_list = []
min = 1000000000
for a in Ai:
    for a2 in Ai[i:]:
        a_gcd = fractions.gcd(a, a2)
        if min > a_gcd:
            min = a_gcd
        if min <= 2:
            print(min)
            quit()
    i += 1

print(min)


### FIXED CODE ###

import fractions

N = int(input())
Ai = list(map(int, input().split()))
if Ai == [Ai[0]] * len(Ai):
    print(Ai[0])
    quit()

#Ai.sort()

i = 1
min = 1000000000
a = Ai[0]
for a2 in Ai[1:]:
    a_gcd = fractions.gcd(a, a2)
    if min > a_gcd:
        min = a_gcd
        if min <= 2:
            print(min)
            quit()

print(min)
### BUGGY CODE ###

N=int(input())
A=[list(map(int, input().split()))  for _ in range(N)]
maxd=0
for i in range(N):
    for j in range(i+1,N):
        maxd=max(maxd,abs(A[i][0]-A[j][0])+abs(A[i][1]-A[j][1]))

print(maxd)

### FIXED CODE ###

N=int(input())
A=[]
B=[]
for _ in range(N):
    x,y=map(int, input().split())
    A.append(x+y)
    B.append(x-y)

A=sorted(A)
B=sorted(B)

print(max(A[-1]-A[0],B[-1]-A[0],A[-1]-A[0],B[-1]-B[0]))
### BUGGY CODE ###

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

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

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
ma = max(a)
sma = sorted(a)[-2]

for i in range(n):
  if a[i] != ma:
    print(ma)
  else:
    print(sma)
### BUGGY CODE ###

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

result = 1

for i in range(k):
    result *= a[k - i]

for i in range(k, n):
    before_result = result
    result /= a[i - k]
    result *= a[i]
    if before_result < result:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

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

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

# -*- coding: utf-8 -*-
def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list

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

li = make_divisor_list(M)

ans = 1
for l in li[::-1]:
    if l >= N:
        ans = max(ans,M//l)
    if ans >= l:
        break

# i = 1
# ans = 0
# tmp = 1000000000

# if M%N == 0:
#     ans = max(ans,M//N)
#     print(ans)
#     exit()

# while M//i >= i and N > i and i <= tmp:
#     if M%i == 0:
#         if tmp == 1000000000:
#             tmp = M//i
#         if M//i >= N:
#             ans = max(ans,i)
#     i += 1

print(ans)


### FIXED CODE ###

N,M = map(int,input().split())
ans = 1
i = 1
while i*i <= M:
    if M%i == 0 and M//N >= i:
        ans = max(ans,i)
        if M //i *N <= M:
            ans = max(ans,M//i)
    i += 1
print(ans)
### BUGGY CODE ###

import heapq
n ,m = map(int,input().split())
arr =list(map(int,input().split()))
for _ in range(m):
  j =int( heapq.nlargest(1,arr)[0])//2
  arr.remove(max(arr))
  arr.append(j)
print(sum(arr))

### FIXED CODE ###

from heapq import heappop, heappush, heapify
n, m = map(int, input().split())
a = list(map(int, input().split()))
q = []
for x in a:
	heappush(q, -x)
for _ in range(m):
	l = heappop(q)
	heappush(q, -((-l)//2))
print(-sum(q))
### BUGGY CODE ###

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

def main():
     n = int(input())
     s = input()
     ans = 0

     for i in range(n):
          first = s[i]
          for j in range(i+1, n):
               if s[j] != first:
                    second = s[j]
                    diff = j - i
                    for k in range(j+1, n):
                         if k - j != diff and s[k] != s[i] and s[k] != s[j]:
                              ans += 1

     print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

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

import queue

def main():
     n = int(input())
     s = input()

     r_list = []
     g_list = []
     b_list = []

     ans = 0

     for i in range(n):
          if s[i] == 'R':
               r_list.append(i)
          elif s[i] == 'G':
               g_list.append(i)
          else:
               b_list.append(i)

     for i in range(n):
          if s[i] == 'R':
               ans += check(i, g_list, b_list)

          if s[i] == 'G':
               ans += check(i, r_list, b_list)

          if s[i] == 'B':
               ans += check(i, r_list, g_list)

     print(ans)

def check(spot, first, second):
     ret = 0
     small_first = []
     big_first = []
     small_second = []
     big_second = []

     for f in first:
          if f < spot: small_first.append(spot - f)
          else: big_first.append(f - spot)

     for s in second:
          if s < spot: small_second.append(spot - s)
          else: big_second.append(s - spot)

     return len(small_first) * len(big_second) + len(small_second) * len(big_first) - len(set(small_first) & set(big_second)) - len(set(small_second) & set(big_first))
     
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def f_c():
    import math
    n = int(input())
    s = input()

    stack, c = 1, 1
    for i in range(1, n*2):
        if s[i]=="B":
            if stack%2==0:
                stack += 1
            else:
                c *= stack
                stack -= 1
        else:
            if stack%2==0:
                c *= stack
                stack -= 1
            else:
                stack += 1
        if stack<0:
            break
    o = 0 if stack!=0 else c*math.factorial(n)
    print(o%(10**9+7))

if __name__ == "__main__":
    f_c()


### FIXED CODE ###

# import sys
# input = sys.stdin.readline
Q = 10**9+7
def main():
    N = int( input())
    S = input()
    left = 0
    ans = 1
    # for i in range(N*2):
    #     s = S[i]
    for s in S:
        if s == "B":
            if left%2 == 0:
                left += 1
            else:
                ans *= left
                left -= 1
        else:
            if left%2 == 1:
                left += 1
            else:
                ans *= left
                left -= 1
        ans %= Q
    if left > 0 or ans == 0:
        print(0)
        return
    for i in range(1,N+1):
        ans *= i
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

MOD = 1000000007
n = int(input())
nums = list(map(int, input().split()))
result = 0
for i in range(n-1):
    for j in range(i+1, n):
        N = nums[i]*nums[j] % MOD
        result += N
        result = result % MOD
print(result)

### FIXED CODE ###

MOD = 1000000007
n = int(input())
nums = list(map(int, input().split()))
x = sum(nums)
y = sum([(nums[i]**2) for i in range(n)])
print(((x**2 - y)//2)% MOD)
### BUGGY CODE ###

N,M = (int(x) for x in input().split())
lr = []
for i in range(1,N+1):
  lr.append(i)
l,r = (int(x) for x in input().split())
d = set(lr[l-1:r])
for i in range(1,M):
  l,r = (int(x) for x in input().split())
  d = d & set(lr[l-1:r])
print(len(d))

  

### FIXED CODE ###

N,M = (int(x) for x in input().split())
R = N
L = 1
for i in range(M):
  l,r = (int(x) for x in input().split())
  if l > L:
    L = l
  if r < R:
    R = r
if R-L < 0:
  print(0)
else:
  print(R-L+1)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


n, m, k = map(int, input().split())
uf = UnionFind(n)
friend = [0] * (n+1)
block = [0] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    friend[a] += 1
    friend[b] += 1
    uf.union(a-1, b-1)
for _ in range(k):
    c, d = map(int, input().split())
    if uf.same(c-1, d-1):
        block[c] += 1
        block[d] += 1

groups = list(uf.all_group_members().values())
w = [0] * (n+1)

for group in groups:
    for member in group:
        member += 1
        w[member] = len(group) - friend[member] - block[member] - 1

print(*w[1:])





### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]


n, m, k = map(int, input().split())
uf = UnionFind(n)
friend = [0] * (n+1)
block = [0] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    friend[a] += 1
    friend[b] += 1
    uf.union(a-1, b-1)

for _ in range(k):
    c, d = map(int, input().split())
    if uf.same(c-1, d-1):
        block[c] += 1
        block[d] += 1

w = [0] * (n+1)

for i in range(1, n+1):
    w[i] = uf.size(i-1) - friend[i] - block[i] - 1

print(*w[1:])
### BUGGY CODE ###

M=10**9+7
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

from collections import defaultdict
N=input()
xs = map(int, input().split())
ys = []
d = defaultdict(int)
for x in xs:
    ps = prime_decomposition(x)
    psd = defaultdict(int)
    for p, c in ps:
        psd[p] = c
        d[p] = max(d[p], c)
    ys.append(psd)
r = 0
for ps in ys:
    t = 1
    for p in d:
        t = (t*(p**(d[p]-ps[p]))%M)%M
    r = (r+t)%M
print(r)


### FIXED CODE ###

M=10**9+7
mod =M
import sys
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
NNN = (10**6)
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

from collections import defaultdict
N=input()
xs = list(map(int, input().split()))
ys = []
d = defaultdict(int)
for x in xs:
    ps = prime_decomposition(x)
    psd = defaultdict(int)
    for p, c in ps:
        psd[p] = c
        d[p] = max(d[p], c)
    ys.append(psd)
g=1
for p in d:
    g=mul(g,p**(d[p])%M)%M
r=0
for x in xs:
    r = (r+mul(g,inverse[x]))%M
print(r%M)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(3001):
  for j in range(3001):
    v = i * R + j * G
    if N >= v and (N - v) % 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 - i * R) // G + 1):
    ball = i * R + j * G
    if N == ball:
      ans += 1
    elif (N - ball) % B == 0:
      ans += 1

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

N, K = map(int, input().split())
x = list(map(int, input().split()))

ans = 10**18
for i in range(N-K+1):
    y = x[i:i+K]
    y0 = x[i]
    yk = x[i+K-1]
    if yk < 0:
        ans = min(ans, abs(y0))
    elif y0 <= 0 and 0 <= yk:
        ans = min(ans, yk-2*y0, 2*yk-y0)
    else:
        ans = min(ans, yk)

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
x = list(map(int, input().split()))

ans = 10**18
for i in range(N-K+1):
    y0 = x[i]
    yk = x[i+K-1]
    if yk < 0:
        ans = min(ans, abs(y0))
    elif y0 <= 0 and 0 <= yk:
        ans = min(ans, yk-2*y0, 2*yk-y0)
    else:
        ans = min(ans, yk)

print(ans)