Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))

for i in range(n):
    p[i] -= 1

v = [False] * n
roop = []

for i in range(n):
    if not v[i]:
        tmp = [i]
        while True:
            t = p[tmp[-1]]
            v[t] = True
            if tmp[0] == t:
                break
            else:
                tmp.append(t)
        roop.append(tmp)

s = []

for li in roop:
    s1 = 0
    for i in li:
        s1 += c[i]
    s.append(s1)

s2 = []

for li in roop:
    tmp = [0]
    for i in li:
        tmp.append(tmp[-1] + c[i])
    for i in li:
        tmp.append(tmp[-1] + c[i])
    s2.append(tmp)

v2 = [-1] * n

for i,li in enumerate(roop):
    for j in li:
        v2[j] = i

ans = -10**18

for i,li in enumerate(roop):
    t = -10**20
    if s[i] <= 0:
        for j in range(len(li)):
            for k1 in range(j+1, j + 1 + min(k, len(li))):
                t = max(t, s2[i][k1] - s2[i][j])
        ans = max(ans, t)
    else:
        cnt = k // len(li)
        if cnt == 0:
            for j in range(len(li)):
                for k1 in range(j+1, j + 1 + min(k, len(li))):
                    t = max(t, s2[i][k1] - s2[i][j])
                    print(j,k1,s2[i][k1] - s2[i][j])
            ans = min(ans, t)
        else:
            for j in range(len(li)):
                for k1 in range(j+1, j + 1 + len(li)):
                    t = max(t, s2[i][k1] - s2[i][j] + s[i] * (k - (k1 - j)) // len(li))
            ans = max(ans, t)

print(ans)


Fixed submission:
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))

for i in range(n):
    p[i] -= 1

v = [False] * n
roop = []

for i in range(n):
    if not v[i]:
        tmp = [i]
        while True:
            t = p[tmp[-1]]
            v[t] = True
            if tmp[0] == t:
                break
            else:
                tmp.append(t)
        roop.append(tmp)

s = []

for li in roop:
    s1 = 0
    for i in li:
        s1 += c[i]
    s.append(s1)

s2 = []

for li in roop:
    tmp = [0]
    for i in li:
        tmp.append(tmp[-1] + c[i])
    for i in li:
        tmp.append(tmp[-1] + c[i])
    s2.append(tmp)

v2 = [-1] * n

for i,li in enumerate(roop):
    for j in li:
        v2[j] = i

ans = -10**20

for i,li in enumerate(roop):
    t = -10**20
    if s[i] <= 0:
        for j in range(len(li)):
            for k1 in range(j+1, j + 1 + min(k, len(li))):
                t = max(t, s2[i][k1] - s2[i][j])
        ans = max(ans, t)
    else:
        for cnt in range(min(len(li), k)+1):
            for j in range(len(li)):
                if k >= cnt:
                    t = max(t, s2[i][cnt+j] - s2[i][j] + s[i] * ((k - cnt) // len(li)))
        ans = max(ans, t)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
n = 0

for i in range(1, 10**6+100):
    n = n * 10 + 7
    if n % k == 0:
        print(i)
        exit()

print(-1)


Fixed submission:
k = int(input())
n = 0

for i in range(1, 10**6+100):
    n = n * 10 + 7
    n %= k
    if n == 0:
        print(i)
        exit()

print(-1)
Buggy python submission (verdict: Runtime Error):
n = int(input())
x = input()

dp = [0] * (n+1)

for i in range(1,n+1):
    tmp = bin(i).count("1")
    dp[i] = dp[i%tmp] + 1

t = x.count('1')
po = []

for i in range(n):
    t1 = t
    if x[i] == '1':
        t1 -= 1
    else:
        t1 += 1
    po.append(t1)

t21 = 0
t22 = 0

for i in range(n):
    if x[i] == '1':
        t21 += pow(2, (n-i-1), t-1)
        t22 += pow(2, (n-i-1), t+1)
        t21 %= t-1
        t22 %= t+1

for i in range(n):
    if x[i] == '1':
        t3 = t21
    else:
        t3 = t22
    if x[i] == '1':
        t3 -= pow(2, (n-i-1), po[i])
    else:
        t3 += pow(2,(n-i-1), po[i])
    print(dp[t3%po[i]]+1)


Fixed submission:
n = int(input())
x = input()

dp = [0] * (n+1)

for i in range(1,n+1):
    tmp = bin(i).count("1")
    dp[i] = dp[i%tmp] + 1

t = x.count('1')
po = []

for i in range(n):
    t1 = t
    if x[i] == '1':
        t1 -= 1
    else:
        t1 += 1
    po.append(t1)

t21 = 0
t22 = 0

for i in range(n):
    if x[i] == '1':
        if t > 1:
            t21 += pow(2, (n-i-1), t-1)
            t22 += pow(2, (n-i-1), t+1)
            t21 %= t-1
            t22 %= t+1
        else:
            t22 += pow(2, (n-i-1), t+1)
            t22 %= t+1

for i in range(n):
    if x[i] == '1':
        t3 = t21
    else:
        t3 = t22
    if po[i] == 0:
        print(0)
    else:
        if x[i] == '1':

            t3 -= pow(2, (n-i-1), po[i])
        else:
            t3 += pow(2,(n-i-1), po[i])
        print(dp[t3%po[i]]+1)
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())

dp = [0] * n
mod = 10**9 + 7

dp[0] = m - n
dp[1] = (m - n)**2 + (m - n + 1)


for i in range(2, n):
    dp[i] = (dp[i-1] + dp[i-2]) * i + dp[i-1] * (m - n)
    dp[i] %= mod

ans = dp[-1]

for i in range(n):
    ans *= (m - i)
    ans %= mod

print(ans)


Fixed submission:
n,m = map(int,input().split())

dp = [0] * n
mod = 10**9 + 7


if n == 1:
    print((m-n) * m % mod)
elif n == 2:
    ans = (m - n)**2 + (m - n + 1)
    for i in range(2):
        ans *= (m - i)
        ans %= mod
    print(ans)
else:
    dp[0] = m - n
    dp[1] = (m - n)**2 + (m - n + 1)


    for i in range(2, n):
        dp[i] = (dp[i-1] + dp[i-2]) * i + dp[i-1] * (m - n)
        dp[i] %= mod

    ans = dp[-1]

    for i in range(n):
        ans *= (m - i)
        ans %= mod

    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    n,s = map(int,input().split())
    a = list(map(int,input().split()))

    mod = 998244353

    dp = [[0]*s for _ in range(n)]

    for i in range(n):
        if a[i]-1 < s:
            dp[i][a[i]-1] += 2**i
            dp[i][a[i]-1] %= mod

    for i in range(n):
        for j in range(s):
            if i != n-1:
                dp[i+1][j] += dp[i][j] * 2
                dp[i+1][j] %= mod
            if i != n-1 and j + a[i+1] < s:
                dp[i+1][j+a[i+1]] += dp[i][j]
                dp[i+1][j+a[i+1]] %= mod

    print(dp[-1][-1]%mod)

if __name__ == '__main__':
    main()


Fixed submission:
import sys
input = sys.stdin.readline

def main():
    n,s = map(int,input().split())
    a = list(map(int,input().split()))

    mod = 998244353

    dp = [[0]*s for _ in range(n)]

    for i in range(n):
        if a[i]-1 < s:
            dp[i][a[i]-1] += pow(2,i,mod)
            dp[i][a[i]-1] %= mod

    for i in range(n):
        for j in range(s):
            if i != n-1:
                dp[i+1][j] += dp[i][j] * 2
                dp[i+1][j] %= mod
            if i != n-1 and j + a[i+1] < s:
                dp[i+1][j+a[i+1]] += dp[i][j]
                dp[i+1][j+a[i+1]] %= mod

    print(dp[-1][-1]%mod)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
n,s = map(int,input().split())
a = list(map(int,input().split()))

mod = 998244353

dp = [[0]*s for _ in range(n)]

for i in range(n):
    if a[i]-1 < n:
        dp[i][a[i]-1] += 2**i
        dp[i][a[i]-1] %= mod

for i in range(n):
    for j in range(s):
        if i != n-1:
            dp[i+1][j] += dp[i][j] * 2
            dp[i+1][j] %= mod
        if i != n-1 and j + a[i+1] < s:
            dp[i+1][j+a[i+1]] += dp[i][j]
            dp[i+1][j+a[i+1]] %= mod

print(dp[-1][-1]%mod)


Fixed submission:
import sys
input = sys.stdin.readline

def main():
    n,s = map(int,input().split())
    a = list(map(int,input().split()))

    mod = 998244353

    dp = [[0]*s for _ in range(n)]

    for i in range(n):
        if a[i]-1 < s:
            dp[i][a[i]-1] += pow(2,i,mod)
            dp[i][a[i]-1] %= mod

    for i in range(n):
        for j in range(s):
            if i != n-1:
                dp[i+1][j] += dp[i][j] * 2
                dp[i+1][j] %= mod
            if i != n-1 and j + a[i+1] < s:
                dp[i+1][j+a[i+1]] += dp[i][j]
                dp[i+1][j+a[i+1]] %= mod

    print(dp[-1][-1]%mod)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
n = int(input())
li = []

for _ in range(n):
    s = input()
    count = 0
    while True:
        if count + 1 >= len(s):
            break
        if s[count] == '(' and s[count+1] == ')':
            s = s[:count] + s[count+2:]
            count = max(0, count-1)
        else:
            count += 1
    li.append(s)

li2 = []
for i in li:
    count = 0
    for j in range(len(i)):
        if i[j] == ')':
            count += 1
        else:
            break
    li2.append((len(i) - count, count))

now = [0,0]
for l,r in li2:
    if l == 0 and r == 0:
        pass
    elif r == 0:
        if now[1] == 0:
            now[0] += l
        elif 0 < now[1] <= l:
            now[0] += l - now[1]
            now[1] = 0
        else:
            now[1] -= l
    elif l == 0:
        if now[0] == 0:
            now[1] += r
        elif 0 < now[0] <= r:
            now[1] += r - now[0]
            now[0] = 0
        else:
            now[0] -= r
    else:
        if min(now[0], l) > min(now[1], r):
            if now[0] > l:
                now[0] -= l
            else:
                now[1] += l - now[0]
                now[0] = 0
        else:
            if now[1] > r:
                now[1] -= r
            else:
                now[0] += r - now[1]
                now[1] = 0

if now[0] == 0 and now[1] == 0:
    print('Yes')
else:
    print('No')


Fixed submission:
s = input()
t = input()

print('Yes' if s == t[:-1] else 'No')
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
a = list(map(int,input().split()))

li = [-1] * n
li[0] = 0
town = [0]
now = 0

for i in range(k):
    now = a[now] - 1
    if li[now] != -1:
        s = li[now]
        break
    else:
        li[now] = i + 1
        town.append(now)

if s == n:
    print(town[-1])
    exit()
town2 = town[s:]
m = len(town2)
l = len(town) - len(town2)

if m == 0:
    print(town[-1])
else:
    print(town2[(k - l) % m]+1)


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

li = [-1] * n
li[0] = 0
town = [0]
now = 0
flag = False

for i in range(k):
    now = a[now] - 1
    if li[now] != -1:
        s = li[now]
        break
    else:
        li[now] = i + 1
        town.append(now)
    if i == k-1:
        flag = True

if flag:
    print(now+1)
    exit()

town2 = town[s:]
m = len(town2)
l = len(town) - len(town2)

print(town2[(k - l) % m]+1)

Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
a = list(map(int,input().split()))

li = [-1] * n
li[0] = 0
town = [0]
now = 0

for i in range(k):
    now = a[now] - 1
    if li[now] != -1:
        s = li[now]
        break
    else:
        li[now] = i + 1
        town.append(now)

town2 = town[s:]
m = len(town2)
l = len(town) - len(town2)

if m == 0:
    print(town[-1])
else:
    print(town2[(k - l) % m]+1)


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

li = [-1] * n
li[0] = 0
town = [0]
now = 0
flag = False

for i in range(k):
    now = a[now] - 1
    if li[now] != -1:
        s = li[now]
        break
    else:
        li[now] = i + 1
        town.append(now)
    if i == k-1:
        flag = True

if flag:
    print(now+1)
    exit()

town2 = town[s:]
m = len(town2)
l = len(town) - len(town2)

print(town2[(k - l) % m]+1)

Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
a = list(map(int,input().split()))

li = [-1] * n
li[0] = 0
town = [0]
now = 0

for i in range(k):
    now = a[now] - 1
    if li[now] != -1:
        s = li[now]
        break
    else:
        li[now] = i + 1
        town.append(now)

town2 = town[s:]
m = len(town2)
l = len(town) - len(town2)

print(town2[(k - l) % m]+1)


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

li = [-1] * n
li[0] = 0
town = [0]
now = 0
flag = False

for i in range(k):
    now = a[now] - 1
    if li[now] != -1:
        s = li[now]
        break
    else:
        li[now] = i + 1
        town.append(now)
    if i == k-1:
        flag = True

if flag:
    print(now+1)
    exit()

town2 = town[s:]
m = len(town2)
l = len(town) - len(town2)

print(town2[(k - l) % m]+1)
Buggy python submission (verdict: Time Limit Exceeded):
n,m,k = map(int,input().split())

mod = 998244353
ans = 0

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    x = 1
    y = 1
    for i in range(r):
        x *= (n - i)
        y *= (i + 1)
        x %= mod
        y %= mod
    return (x * modinv(y, mod)) % mod


for i in range(k+1):
    ans += m * combination(n-1, i, mod) * pow(m-1, n-i-1, mod)
    ans %= mod

print(ans)



Fixed submission:
import sys

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

n,m,k = map(int,input().split())

mod = 998244353
ans = 0

comb = Combination(2*10**5)


for i in range(k+1):
    ans += m * comb(n-1, i) * pow(m-1, n-i-1, mod)
    ans %= mod

print(ans)
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())

li = [True] * n

count = 0
for sub1 in range(1,m+1):
    while True:
        if li[count]:
            print(count+1, count + sub1 + 1)
            li[count] = False
            li[count+sub1] = False
            break
        else:
            count += 1


Fixed submission:
n,m = map(int,input().split())

li = [True] * n

a = 1 + m
if m % 2 == 0:
    for i in range(m//2):
        print(1+i, a-i)
    for i in range(m//2):
        print(a+1+i, a+m-i)

else:
    for i in range((m+1)//2):
        print(1+i, a-i)
    for i in range(m//2):
        print(a+1+i, a+m-i)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)

li = [int(s[-1])]

for i in range(n-1):
    t = int(s[-i-2])
    li.append((li[-1] + t * 10 ** (i+1)) % 2019)

dict1 = {}
for i in li:
    if i in dict1:
        dict1[i] += 1
    else:
        dict1[i] = 1

ans = 0

for v in dict1.values():
    ans += v * (v-1) // 2

if 0 in dict1:
    ans += dict1[0]

print(ans)


Fixed submission:
s = input()
n = len(s)

li = [0] * n
li[0] = int(s[-1])

for i in range(n-1):
    t = int(s[-i-2])
    li[i+1] = (li[i] + t * pow(10, i+1, 2019)) % 2019

dict1 = {}
for i in li:
    if i in dict1:
        dict1[i] += 1
    else:
        dict1[i] = 1

ans = 0

for v in dict1.values():
    ans += v * (v-1) // 2

if 0 in dict1:
    ans += dict1[0]

print(ans)

Buggy python submission (verdict: Runtime Error):
s = input()
n = len(s)

li = [int(s[-1])]

for i in range(n-1):
    t = int(s[-i-2])
    li.append((li[-1] + t * 10 ** (i+1)) % 2019)

dict1 = {}
for i in li:
    if i in dict1:
        dict1[i] += 1
    else:
        dict1[i] = 1

ans = 0

for v in dict1.values():
    ans += v * (v-1) // 2

print(ans + dict1[0])


Fixed submission:
s = input()
n = len(s)

li = [0] * n
li[0] = int(s[-1])

for i in range(n-1):
    t = int(s[-i-2])
    li[i+1] = (li[i] + t * pow(10, i+1, 2019)) % 2019

dict1 = {}
for i in li:
    if i in dict1:
        dict1[i] += 1
    else:
        dict1[i] = 1

ans = 0

for v in dict1.values():
    ans += v * (v-1) // 2

if 0 in dict1:
    ans += dict1[0]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd

k = int(input())
ans = 0

for i in range(k):
    for j in range(k):
        for ii in range(k):
            ans += gcd(i+1,gcd(j+1,ii+1))

print(ans)


Fixed submission:
from math import gcd

k = int(input())
ans = 0

for i in range(k):
    for j in range(k):
        for ii in range(k):
            ans += gcd(i+1,gcd(j+1,ii+1))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,x,y = map(int,input().split())

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数, w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

dis = [[float('inf')] * n for _ in range(n)]
ans = [0] * (n-1)
for i in range(n):
    for j in range(n):
        if abs(i - j) == 1:
            dis[i][j] = 1
dis[x-1][y-1] = 1
dis[y-1][x-1] = 1

for i in range(n):
    d = dijkstra(i, n, n, dis)
    for j in d:
        if j > 0:
            ans[j-1] += 1

for i in ans:
    print(i//2)


Fixed submission:
import heapq
n,x,y = map(int,input().split())

roots = [[] for _ in range(n)]

for i in range(n):
    if i == 0:
        roots[i].append(1)
    elif i == n - 1:
        roots[i].append(n-2)
    else:
        roots[i].append(i-1)
        roots[i].append(i+1)

roots[x-1].append(y-1)
roots[y-1].append(x-1)
ans = [0] * (n-1)

for i in range(n):
    hq = []
    dis = [-1]* n
    dis[i] = 0
    heapq.heappush(hq, (0,i))
    while hq:
        dis1, place = heapq.heappop(hq)
        for j in roots[place]:
            if dis[j] == -1 or dis[j] > dis1 + 1:
                dis[j] = dis1 + 1
                heapq.heappush(hq, (dis1+1, j))
    for j in dis:
        if j > 0:
            ans[j-1] += 1

for i in ans:
    print(i//2)
Buggy python submission (verdict: Time Limit Exceeded):
n,m,k = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
cd = [list(map(int,input().split())) for _ in range(k)]

edges = [[] for _ in range(n)]
cd2 = [[] for _ in range(n)]
friends = []
count = [-1] * n
g_count = 0
ans = [0] * n

for a,b in ab:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

for c,d in cd:
    cd2[c-1].append(d-1)
    cd2[d-1].append(c-1)


for i in range(n):
    if count[i] == -1:
        count[i] = g_count
        g = [i]
        q = [i]
        while q:
            l = q.pop(-1)
            for f in edges[l]:
                if count[f] == -1:
                    q.append(f)
                    g.append(f)
                    count[f] = g_count

        friends.append(g)
        g_count += 1

for i in range(n):
    x = len(set(friends[count[i]]) & set(edges[i]))
    y = len(set(friends[count[i]]) & set(cd2[i]))
    z = len(set(friends[count[i]]) & set(edges[i]) & set(cd2[i]))
    ans[i] = len(friends[count[i]]) - (x + y - z) - 1

for i in range(n):
    print(ans[i], end = ' ')


Fixed submission:
import sys

n,m,k = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
cd = [list(map(int,input().split())) for _ in range(k)]

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 size(self, x):
        return -self.parents[self.find(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()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(n)
ans = [0]*n
cnt = [0]*n

for a,b in ab:
    uf.union(a-1, b-1)
    cnt[a-1] += 1
    cnt[b-1] += 1

for i in range(n):
    ans[i] = uf.size(i)

for c,d in cd:
    if uf.same(c-1, d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1

for i in range(n):
    print(ans[i] - cnt[i] - 1, end = ' ')
Buggy python submission (verdict: Runtime Error):
print(‘x’*len(input()))

Fixed submission:
s = input()
print('x' * len(s))
Buggy python submission (verdict: Time Limit Exceeded):
import copy

n = int(input())
a = list(map(int,input().split()))
d = {}
ans = 0
mod = 10**9 + 7

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

arr = []
for i in a:
    ar = factorization(i)
    arr.append(ar)
    for j,k in ar:
        if j not in d:
            d[j] = k
        else:
            d[j] = max(k, d[j])

for i in arr:
    d2 = copy.copy(d)
    tmp = 1
    for j,k in i:
        d2[j] -= k
    for k,v in d2.items():
        tmp *= pow(k,v,mod)
    ans += tmp
    ans %= mod

print(ans)


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
d = {}
ans = 0
mod = 10**9 + 7

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

for i in a:
    arr = factorization(i)
    for j,k in arr:
        if j not in d:
            d[j] = k
        else:
            d[j] = max(k, d[j])

l = 1
for k,v in d.items():
    l *= pow(k,v,mod)
    l %= mod

for i in a:
    ans += l * pow(i, mod-2, mod)
    ans %= mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))

mod = 10 ** 9 + 7

lcm1 = 1

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd (a, b)

for i in a:
    lcm1 = lcm(lcm1, i)

ans = 0

for i in a:
    ans += lcm1 // i

print(ans%mod)


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
d = {}
ans = 0
mod = 10**9 + 7

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

for i in a:
    arr = factorization(i)
    for j,k in arr:
        if j not in d:
            d[j] = k
        else:
            d[j] = max(k, d[j])

l = 1
for k,v in d.items():
    l *= pow(k,v,mod)
    l %= mod

for i in a:
    ans += l * pow(i, mod-2, mod)
    ans %= mod

print(ans)