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

def solve(n, g):
    mod = 10 ** 9 + 7

    dp = [[1] * 2 for _ in range(n)]

    # dp[j][0/1] := 頂点jを0/1とする場合のjを親とする部分木の塗り方の状態数
    # dp[j][0] = reduce(mul, (dp[k][0] + dp[k][1] for k in g[j]))
    # dp[j][1] = reduce(mul, (dp[k][0] for k in g[j]))

    def dfs(v, parent=-1):
        for u in g[v]:
            if u == parent:
                continue
            dfs(u, v)
            dp[v][0] = dp[v][0] * (dp[u][0] + dp[u][1]) % mod
            dp[v][1] = dp[v][1] * dp[u][0] % mod

    dfs(0)

    return sum(dp[0]) % mod


if __name__ == '__main__':
    import sys

    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする


### FIXED CODE ###

def solve(n, g):
    mod = 10 ** 9 + 7

    def dfs(v):
        checked[v] = True

        w = 1
        b = 1
        for u in g[v]:
            if checked[u]:
                continue
            uw, ub = dfs(u)
            w = w * (uw + ub) % mod
            b = b * uw % mod
        return w, b

    stack = [0]
    order = []
    parent = [-1] * n
    checked = [False] * n
    checked[0] = True

    while stack:
        v = stack.pop()
        order.append(v)
        for u in g[v]:
            if checked[u]:
                continue
            checked[u] = True
            parent[u] = v
            stack.append(u)

    order.reverse()

    checked = [False] * n

    dp_w = [1] * n
    dp_b = [1] * n

    for v in order:
        checked[v] = True
        par = parent[v]
        if par == -1:
            continue
        dp_w[par] = (dp_w[par] * (dp_w[v] + dp_b[v])) % mod
        dp_b[par] = (dp_b[par] * dp_w[v]) % mod

    v = order[-1]
    return (dp_w[v] + dp_b[v]) % mod


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする
# 2次元配列でdpするより、1次元*2本の方が若干速い
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[34]:


import numpy as np
N = int(input())
S = input()
"""
5
ababa
2

13
strangeorange
5
"""


# In[41]:


dp = np.zeros((N+1, N+1), dtype=np.uint32)


# In[43]:


max_cont = 0
for i in range(N)[::-1]:
    for j in range(i+1, N)[::-1]:
        if S[i] == S[j]:
            dp[i,j] = min(dp[i+1, j+1]+1, j-i)
            max_cont = max(max_cont, dp[i, j])
        else:
            continue


# In[44]:


print(max_cont)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[49]:


#import numpy as np
N = int(input())
S = input()
"""
5
ababa
2

13
strangeorange
5
"""


# In[54]:


i = 0
j = 1
max_cont = 0

while j < N:
    if S[i:j] in S[j:]:
        max_cont = max(max_cont, len(S[i:j]))
        j += 1
    else:
        i += 1
    if i == j:
        i += 1
        j += 2


# In[55]:


print(max_cont)


# In[ ]:
### BUGGY CODE ###

n, k, q = map(int, input().split())
alist = []
for i in range(q):
  a = int(input())
  alist.append(a - 1)
pscore = [k] * n
for j in range(q):
  for k in range(n):
    if alist[j] != k:
      pscore[k] -= 1
for k in range(n):
  if pscore[k] <= 0:
    print('No')
  else:
    print('Yes')

### FIXED CODE ###

n, k, q = map(int, input().split())
alist = []
for i in range(q):
  a = int(input())
  alist.append(a - 1)
pscore = [0] * n
for j in range(q):
  pscore[alist[j - 1]] += 1
for i in range(n):
  pscore[i] -= (q - k)
  if pscore[i] <= 0:
    print('No')
  else:
    print('Yes')
### BUGGY CODE ###

n= int(input())
ans=0
nn = int((n-1)//2)+1
for i in range(2,nn):
    for j in range(2,nn):
        if i*j>n-1:
            break
        else:
            ans += 1

ans += (n-1-1)*2
print(ans+1)

### FIXED CODE ###

n= int(input())
ans=0
nn = int((n-1)//2)+1
for i in range(2,nn):
    for j in range(i,nn):
        if i*j>n-1:
            break
        else:
            if i==j:
                ans += 1
            else:
                ans+=2
# a or b =1
ans += (n-1-1)*2
print(ans+1)
### BUGGY CODE ###

# -- coding: utf-8 --
import math
N, H = map(int, input().split())
sl = []
th = []
for i in range(N):
    s, t = map(int, input().split())
    sl.append(s)
    th.append(t)
turn = 0
thm = list(filter(lambda x:x>max(sl), th))
thdec = sorted(th, reverse=True)

if sum(thdec) >= H:
    while H > 0:
        H = H - max(thdec)
        thdec.pop(0)
        turn += 1
else:
    turn = math.ceil((H - sum(thm)) / max(sl)) + len(thm)

print(turn)

### FIXED CODE ###

# -- coding: utf-8 --
import math
N, H = map(int, input().split())
th = []
sl_max = 0
for i in range(N):
    s, t = map(int, input().split())
    sl_max = max(sl_max, s)
    th.append(t)
turn = 0
thdec = sorted(th, reverse=True)

for i in range(len(thdec)):
    if thdec[i] >= sl_max:
        H -= thdec[i]
        turn += 1
        if H <= 0:
            break
    else:
        break

if H > 0:
    turn += math.ceil(H / sl_max)

print(turn)
### BUGGY CODE ###

A, B, C, D = map(int, input().split())

count = 0

for i in range(A, B+1):
    if i % C != 0 and i % D != 0:
        count += 1

print(count)

### FIXED CODE ###

import fractions

a, b, c, d = map(int, input().split())

# 最小公倍数を求める
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def cal(num, a, b):
    x = num // a
    y = num // b
    z = num // (lcm(a, b))
    return num - (x + y - z)

num_a = cal(b, c, d)
num_b = cal(a-1, c, d)

print(num_a - num_b)
### BUGGY CODE ###

import bisect

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

L.sort()

buff = []
ll = []


for i in range(N):
    l_b = []
    for j in range(i+1, N):
        l_b.append(L[i]+L[j])
        ll.append(L[i]+L[j])
    if i != N-1:
        buff.append(l_b)
# buff.sort()
# print(L)
# print(buff)

ans = 0
_len = len(buff)

for i in range(_len):
    for j in range(len(buff[i])):
        index = bisect.bisect_left(L[i+j+1+1:], buff[i][j])
        # print(L[i+j+1+1:])
        # print(index, buff[i][j])
        ans += index
print(ans)


# for i in range(N):
#     index = bisect.bisect_left(buff, L[i])
#     print(index)
#     ans += index
# print(ans)


### FIXED CODE ###

import bisect

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

L.sort()

buff = []
# ll = []


for i in range(N):
    l_b = []
    for j in range(i+1, N):
        l_b.append(L[i]+L[j])
        # ll.append(L[i]+L[j])
    if i != N-1:
        buff.append(l_b)
# buff.sort()
# print(L)
# print(buff)

ans = 0
_len = len(buff)

for i in range(_len):
    for j in range(len(buff[i])):
        index = bisect.bisect_left(L[i+j+1+1:], buff[i][j])
        # print(L[i+j+1+1:])
        # print(index, buff[i][j])
        ans += index
print(ans)


# for i in range(N):
#     index = bisect.bisect_left(buff, L[i])
#     print(index)
#     ans += index
# print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
count = 0
for i in range(M):
    a,b = map(int,input().split())
    if count == 0:
        set = {i for i in range(a,b+1)}
        count = 1
    else:
        set2 ={i for i in range(a,b+1)}
        set = set & set2
print(len(set))

### FIXED CODE ###

N,M = map(int,input().split())
count = 0
for i in range(M):
    a,b = map(int,input().split())
    if count == 0:
        L = a
        R = b
        count = 1
    else:
        if L < a:
            L =a
            if L>R:
                break
        if R > b:
            R = b
            if R < L:
                break
if M == i+1:
    print(R-L+1)
else:
    print(0)
### BUGGY CODE ###

S = input()
N = len(S)
dp = []
for _ in range(N+1):
    dp.append([0] * 13)
dp[0][0] = 1

for i in range(1, N+1):
    X = S[N-i]
    if X == '?':
        for j in range(10):
            X = (j * pow(10, i-1, 13)) % 13
            for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
                Y = dp[i-1][k]
                Z = (X + k) % 13  # 新たなあまり
                dp[i][Z] += Y

    else:
        X = int(X)
        X = (X * pow(10, i-1, 13)) % 13
        for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
            Y = dp[i-1][k]
            Z = (X + k) % 13  # 新たなあまり
            dp[i][Z] += Y

print(dp[-1][5] % 1000000007)


### FIXED CODE ###

S = input()
N = len(S)
dp = []
for _ in range(N+1):
    dp.append([0] * 13)
dp[0][0] = 1
p = 10**9+7

for i in range(1, N+1):
    X = S[N-i]
    if X == '?':
        for j in range(10):
            X = (j * pow(10, i-1, 13)) % 13
            for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
                Y = dp[i-1][k]
                Z = (X + k) % 13  # 新たなあまり
                dp[i][Z] += Y % p

    else:
        X = int(X)
        X = (X * pow(10, i-1, 13)) % 13
        for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
            Y = dp[i-1][k]
            Z = (X + k) % 13  # 新たなあまり
            dp[i][Z] += Y % p

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

n=int(input())
a=list(map(int,input().split()))
b=set(a)
cnt=0
for i in b:
  x=a.count(i)
  c=x*(x-1)//2
  cnt+=c
for i in a:
  x=a.count(i)
  print(cnt+(1-x))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
cnt=0
for i in a:
  b[i-1]+=1
for i in b:
  cnt+=i*(i-1)//2
for i in a:
  print(cnt+(1-b[i-1]))
### BUGGY CODE ###

import bisect
X, Y, X, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A.sort()
B.sort()
C.sort()
ans1 = []
ans2 = []
for i in range(min(K,len(A))):
  for j in range(min(K,len(B))):
    ans1.append(A[i]+B[j])
ans1.sort(reverse=True)
for i in range(min(K,len(ans1))):
  for k in range(min(K,len(C))):
    ans2.append(ans1[i]+C[k])
ans2.sort(reverse=True)  
for i in range(K):
  print(ans2[i])

### FIXED CODE ###

from heapq import heappop, heappush,heapify
X,Y,Z,K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
H = []
heappush(H,[-1*(A[0]+B[0]+C[0]),0,0,0])
count = 1
memo = []
while H and count <= K:
  tmp,i,j,k = heappop(H)
  print(-1*tmp)
  count += 1
  if i+1 < X and ((i+1,j,k) not in memo):
    heappush(H,[-1*(A[i+1]+B[j]+C[k]),i+1,j,k])
    memo.append((i+1,j,k))
  if j+1 < Y and ((i,j+1,k) not in memo):
    heappush(H,[-1*(A[i]+B[j+1]+C[k]),i,j+1,k])
    memo.append((i,j+1,k))
  if k+1 < Z and ((i,j,k+1) not in memo):
    heappush(H,[-1*(A[i]+B[j]+C[k+1]),i,j,k+1])
    memo.append((i,j,k+1))
### BUGGY CODE ###

s = input()[::-1]
ans = 0
data = [0 for _ in range(2019)]
now = 0
data[0] = 1
for i,x in enumerate(s):
    now += int(x)*10**i
    now %= 2019
    data[now] += 1
    #print(now)

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

print(ans)

### FIXED CODE ###

s = input()[::-1]
n = len(s)
ans = 0
data = [0 for _ in range(2019)]
now = 0
data[0] = 1
q = [1]
x = 1
for i in range(n):
    x *= 10
    x %= 2019
    q.append(x)

for i,x in enumerate(s):
    now += int(x)*q[i]
    now %= 2019
    data[now] += 1
    #print(now)

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

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


def solve(N, Q, ABs, PXs):
    values = {i: 0 for i in range(N + 1)}
    ans = [-1 for i in range(N + 1)]
    vertexes = {}
    for a, b in ABs:
        vertexes.setdefault(a, []).append(b)
        vertexes.setdefault(b, []).append(a)

    for p, x in PXs:
        values[p] += x

    queue = []
    queue.append((1, 0))
    while queue:
        index, parent_value = queue.pop()
        value = parent_value + values[index]
        ans[index] = value
        for child in vertexes[index]:
            if ans[child] == -1:
                queue.append((child, value))
    return " ".join([str(a) for a in ans[1:]])


assert (solve(4, 3, [(1, 2), (2, 3), (2, 4)], [(2, 10), (1, 100), (3, 1)]) == "100 110 111 110")
assert (solve(6 , 2 , [(1, 2), (1, 3), (2, 4), (3, 6), (2, 5)] , [(1, 10), (1, 10)]) == "20 20 20 20 20 20")

if __name__ == "__main__":
    N, Q = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    PXs = [tuple(map(int, input().split(" "))) for _ in range(Q)]
    print(solve(N, Q, ABs, PXs))


### FIXED CODE ###


def solve(N, Q, ABs, PXs):
    values = {i: 0 for i in range(N + 1)}
    ans = [-1 for i in range(N + 1)]
    vertexes = {}
    for a, b in ABs:
        vertexes.setdefault(a, []).append(b)
        vertexes.setdefault(b, []).append(a)

    for p, x in PXs:
        values[p] += x

    queue = []
    queue.append((1, 0))
    while queue:
        index, parent_value = queue.pop()
        value = parent_value + values[index]
        ans[index] = value
        for child in vertexes[index]:
            if ans[child] == -1:
                queue.append((child, value))
    return " ".join([str(a) for a in ans[1:]])


if __name__ == "__main__":
    N, Q = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    PXs = [tuple(map(int, input().split(" "))) for _ in range(Q)]
    print(solve(N, Q, ABs, PXs))
### BUGGY CODE ###

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

ans = 300000
lst = []
for i in range(n):
    tmp = s[:i].count("W") + s[i+1:].count("E")
    ans = min(ans,tmp)
    
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
s_min = s[1:].count("E")
s_now = s[1:].count("E")

for i in range(1,n):
    if s[i-1] == "E" and s[i] == "E":
        s_now -= 1
    if s[i-1] == "W" and s[i] == "W":
        s_now += 1
    s_min = min(s_min, s_now)
print(s_min)
### BUGGY CODE ###

n = input()
As = list(map(int, input().split()))
import math
gcd = As[0]
for a in As[1:]:
    tmp = gcd
    gcd = math.gcd(tmp, a)

if gcd > 1:
    print("not coprime")
    exit()
flg = 0
lcd = As[0]
prod = As[0]
for a in As[1:]:
    if math.gcd(a,lcd) != 1:
        print("setwise coprime")
        exit()
    lcd = a*lcd//math.gcd(a,lcd)
 
print("pairwise coprime")

    

### FIXED CODE ###

import math

n = input()
As = list(map(int, input().split()))
gcd = As[0]
for a in As[1:]:
    tmp = gcd
    gcd = math.gcd(tmp, a)

if gcd > 1:
    print("not coprime")
    exit()

era = [0] * (10**6 + 1)
for a in As:
    era[a] += 1
for d in range(2, 10**6+1):
    data = [i for i in range(d,10**6+1,d)]
    cnt = 0
    for i in data:
        cnt += era[i] 
    if cnt > 1:
        print("setwise coprime")
        exit()
print("pairwise coprime")
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=a[0]
for i in a[1:n]:
    ans*=i
print(-1 if ans >(10**18) else ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    b*=a[i]
    if b>10**18:
        print(-1)
        exit()
print(b)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(n)]
    x = sorted(xy, key=lambda a: a[0])
    y = sorted(xy, key=lambda a: a[1])

    res = 10**20
    for l in range(n):
        for r in range(l+1, n):
            for b in range(n):
                for t in range(b+1, n):
                    cnt = 0
                    for vx, vy in xy:
                        if x[l][0] <= vx <= x[r][0] and y[b][1] <= vy <= y[t][1]:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, (x[r][0]-x[l][0])*(y[t][1]-y[b][1]))
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(n)]
    x = sorted(xy, key=lambda a: a[0])
    y = sorted(xy, key=lambda a: a[1])

    res = 10**20
    for l in range(n):
        for r in range(l+1, n):
            for b in range(n):
                for t in range(b+1, n):
                    cnt = 0
                    for vx, vy in x[l:r+1]:
                        if y[b][1] <= vy <= y[t][1]:
                            cnt += 1
                        if cnt >= k:
                            res = min(res, (x[r][0]-x[l][0])*(y[t][1]-y[b][1]))
                            break
    print(res)

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

import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    weights = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        weights[p-1] += x

    ans = [0] * N
    ans[0] = weights[0]
    visited = [False] * N
    def f(a, node):
        visited[node] = True
        for nt in G[node]:
            if visited[nt]:
                continue
            b = a + weights[nt]
            ans[nt] = b
            f(b, nt)

    f(weights[0], 0)
    for a in ans:
        print(a, end=' ')
    print()


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    G = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].add(b-1)
        G[b-1].add(a-1)

    weights = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        weights[p-1] += x

    ans = [0] * N
    ans[0] = weights[0]
    visited = [False] * N
    def f(a, node):
        visited[node] = True
        for nt in G[node]:
            if visited[nt]:
                continue
            b = a + weights[nt]
            ans[nt] = b
            f(b, nt)
        return  0

    f(weights[0], 0)
    return ' '.join(map(str, ans))


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

from sys import stdin
import math
import itertools
import re
 
 
def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]
 
dp = {}
 
def solve(input_string):
    S = input_string[1]
    intMatrix = makeIntMatrix(input_string[2:])
    #print(input_string[2:])
    for line in intMatrix:
        l, r = line
        #print(l, r)
        #print(S[l:r+1])
        #cnt = len(re.findall(r'AC', S[l-1:r]))
        cnt = cntAC(l, r, S[l-1:r])
        print(cnt)
    return
 
 
def cntAC(l, r, t):
    if l+r not in dp:
        dp[l+r] = len(t.split('AC'))-1
    return dp[l+r]
 
 
def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    #print(answer)
 
 
if __name__ == '__main__':
    main()


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t=[0]*(N+1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

from sys import stdin
from collections import defaultdict

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = defaultdict(int)
ans = 0

for i in range(N):
    tmp = 1
    a = A[i]
    g_tmp = defaultdict(int)
    while tmp <= A[i] ** 0.5:
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            if tmp not in g_tmp:
                g_tmp[tmp] = 1
            else:
                g_tmp[tmp] += 1
        tmp += 1
    if a > 1:
        if a not in g_tmp:
            g_tmp[a] = 1
        else:
            g_tmp[a] += 1

    for j in g_tmp:
        if j not in g:
            g[j] = g_tmp[j]
        else:
            g[j] = max(g[j], g_tmp[j])

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod) % mod
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

### FIXED CODE ###

from sys import stdin
from collections import defaultdict

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = defaultdict(int)

for i in range(N):
    tmp = 1
    a = A[i]
    while tmp <= A[i] ** 0.5:
        cnt = 0
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            cnt += 1
        if cnt > 0:
            g[tmp] = max(g[tmp], cnt)
        tmp += 1
    if a > 1:
        if a not in g:
            g[a] = 1

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod)
    l %= mod
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

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

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

max_val = 0
max_idx = 0
for i in range(1,N-K+2):
  tmp = sum(p[i-1:i-1+K])
  if tmp > max_val:
    max_val = tmp
    max_idx = i

expect = 0.0
for i in range(max_idx, max_idx+K):
  tmp = 0.0
  for j in range(1,p[i-1]+1):
    tmp += j
  expect += tmp/p[i-1]
print(expect)

### FIXED CODE ###

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

max_val = 0
max_idx = 0
tmp = 0
for i in range(1,N-K+2):
  if i == 1:
    tmp = sum(p[i-1:i-1+K])
  else:
    tmp = tmp - p[i-2] + p[i-2+K]
  if tmp > max_val:
    max_val = tmp
    max_idx = i

p = p[max_idx-1:max_idx-1+K]
p.sort()
prev_tmp = 0.0
expect = 0.0
for i in range(len(p)):
  tmp = 0.0
  if i == 0:
    for j in range(1,p[i]+1):
      tmp += j
    expect += tmp/p[i]
    prev_tmp = tmp
  else:
    tmp = prev_tmp
    for j in range(p[i-1]+1,p[i]+1):
      tmp += j
    expect += tmp/p[i]
    prev_tmp = tmp
print(expect)
### BUGGY CODE ###

n = int(input())
a = list(map(str,input().split()))
for i in range(1,n+1):
    print(a.count(str(i)))
    a = [j for j in a if j != str(i)]

### FIXED CODE ###

n = int(input())
a = list(map(str,input().split()))
from collections import Counter
x = Counter(a)
for i in range(1,n+1):
    print(x[str(i)])
### BUGGY CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [[0] * 2] * m

for i in range(m):
    bc[i] = list(map(int, input().split()))

a.sort()

for i in range(m):
    for j in range(bc[i][0], -1, -1):
        m = min(a)

        if (j == 0 or bc[i][1] <= m):
            break
        else:
            a[a.index(m)] = bc[i][1]
            bc[i][0] -= 1

print(sum(a))


### FIXED CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [[0] * 2] * m

for i in range(m):
    bc[i] = list(map(int, input().split()))

a.sort()
bc = sorted(bc, key=lambda x: -x[1])
new = []

cnt = 0

for e in bc:
    new += [e[1]] * e[0]
    cnt += e[0]

    if (n <= cnt):
        break

for i in range(min(n, cnt)):
    a[i] = max(a[i], new[i])

print(sum(a))