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

from sys import stdin, gettrace
if not gettrace():
    def input():
        return next(stdin)[:-1]
# def input():
#    return stdin.buffer.readline()
def main():
    s1=input()
    s2=input()
    n1,n2=len(s1),len(s2)
    dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
    for i in range(n1,-1,-1):
        for j in range(n2,-1,-1):
            if i==n1 or j==n2:
                dp[i][j]=""
            else:
                if s1[i]==s2[j]:
                    dp[i][j]=s1[i]+dp[i+1][j+1]
                else:
                    x=dp[i][j+1]
                    y=dp[i+1][j]
                    if len(x)>len(y):
                        dp[i][j]=x
                    else:
                        dp[i][j]=y
    print(dp[0][0])
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

s1=input()
s2=input()
n1,n2=len(s1),len(s2)
dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
for i in range(n1,-1,-1):
    for j in range(n2,-1,-1):
        if i==n1 or j==n2:
            dp[i][j]=0
        else:
            if s1[i]==s2[j]:
                dp[i][j]=1+dp[i+1][j+1]
            else:
                dp[i][j]=max(dp[i][j+1],dp[i+1][j])
n=""
i,j=0,0
while i<n1 and j<n2:
    if dp[i][j]==dp[i+1][j]:
        i+=1
    elif dp[i][j]==dp[i][j+1]:
        j+=1
    else:
        n+=s1[i]
        i+=1
        j+=1
print(n)
### BUGGY CODE ###

import itertools
import operator

N, K = [int(x) for x in input().split(" ")]
A = [int(x) for x in input().split(" ")]

pro = [1] + list(itertools.accumulate(A, func=operator.mul))
# print(pro)
# print(pro[3] // pro[0])
# print(pro[4] // pro[1])
# print(pro[5] // pro[2])
# print(pro)
# for i in range(K + 1, N + 1):
#     if (pro[i] // pro[i - K]) > (pro[i - 1] // pro[i - K - 1]):
#         print("Yes")
#     else:
#         print("No")
for i in range(K + 1, N + 1):
    if pro[i] * pro[i - K - 1] > pro[i - K] * (pro[i - 1]):
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N, K = [int(x) for x in input().split(" ")]
A = [int(x) for x in input().split(" ")]


for i in range(K, N):
    if A[i - K] < A[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n, m = map(int, input().split())
pp = list(map(int, input().split()))
xyxy = [list(map(int, input().split())) for _ in range(m)]

class UnionFind(list) :
    def __init__(self, n) :
        super().__init__(range(n))

    def find(self, i) :
        if self[i] == i : return i
        self[i] = self.find(self[i])
        return self[i]

    def union(self, x, y) :
        from copy import copy
        x = self.find(x)
        y = self.find(y)
        self.new = copy(self)
        self.new[y] = x
        return self.new

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

uf = UnionFind(n)
for x, y in xyxy :
    uf = uf.union(x-1, y-1)
for i in range(n) :
    uf.find(i)

d = {}
for i, k in enumerate(uf) :
    if k not in d :
        d[k] = {i}
    else :
        d[k].add(i)

e = {}
for k, set0 in d.items():
    e[k] = set()
    for i in set0 :
        e[k].add(pp[i]-1)

ans = 0
for k in d.keys() :
    set0 = d[k]
    set1 = e[k]
    ans += len(set0&set1)

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
pp = list(map(int, input().split()))
xyxy = [list(map(int, input().split())) for _ in range(m)]

class UnionFind(list) :
    def __init__(self, n) :
        super().__init__(range(n))

    def find(self, i) :
        if self[i] == i : return i
        self[i] = self.find(self[i])
        return self[i]

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

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

uf = UnionFind(n)
for x, y in xyxy :
    uf.union(x-1, y-1)
for i in range(n) :
    uf.find(i)

d = {}
for i, k in enumerate(uf) :
    if k not in d :
        d[k] = {i}
    else :
        d[k].add(i)

e = {}
for k, set0 in d.items():
    e[k] = set()
    for i in set0 :
        e[k].add(pp[i]-1)

ans = 0
for k in d.keys() :
    set0 = d[k]
    set1 = e[k]
    ans += len(set0&set1)

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

import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))


N = int(input())
A = [int(x) for x in input().split()]
A = [0] + A

R = []

dl = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    cnt = 1
    while i * cnt <= N:
        dl[i][i * cnt] = 1
        cnt += 1

for i in range(N, 0, -1):
    if A[i] == 1:
        R.append(i)
        for j in range(i, 0, -1):
            A[j] = (A[j] + 1) % 2

print(len(R))
print(" ".join([str(i) for i in R]))

# print(R)

### FIXED CODE ###

import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)


# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

def divisor_list(n):
    ret = set()
    i = 1
    while i * i <= n:
        if n % i == 0:
            ret.add(i)
            ret.add(n // i)
        i += 1
    return ret


N = int(input())
tmp = [int(x) for x in input().split()]
A = [-999]
for a in tmp:
    A.append(a)

B = []

for i in range(N, 0, -1):
    # print(i)
    if A[i] == 1:
        B.append(str(i))
        DL = divisor_list(i)
        for j in DL:
            A[j] = (A[j] + 1) % 2

print(len(B))
print(" ".join(B))

pass
### BUGGY CODE ###

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

dp=[0]*(S+1)
dp[0]=pow(2,N,MOD)
div=pow(2,MOD-2,MOD)

m=0
for a in A:
    m+=a
    for i in range(min(m,S),a-1,-1):
        dp[i]=(dp[i]+dp[i-a]*div)%MOD
print(dp[S])

### FIXED CODE ###

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

def f(N,S,A):
    MOD=998244353
    dp=[0]*(S+1)
    dp[0]=pow(2,N,MOD)
    div=pow(2,MOD-2,MOD)
    m=0
    for a in A:
        m+=a
        for i in range(min(m,S),a-1,-1):
            dp[i]=(dp[i]+dp[i-a]*div)%MOD
    return dp[S]

print(f(N,S,A))
### BUGGY CODE ###

import math
from functools import reduce
from collections import deque, Counter
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def prime_factorize(n):
    """
    素因数分解
    
    Sample:
        prime_factorize(36)
        => [2, 2, 3, 3]

        collections.Counter(prime_factorize(36))
        => {2:2, 3:2}
    """
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

    if len(arr) == 0:
        arr.append((n, 1))
    return arr

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

INF = 999999999999999999999999
MOD = 10**9+7

n,*A = get_all_int()
C = dict(Counter(A))
keys = C.keys()
# log(C)

ans = 0

for i,a in enumerate(A):
    div = make_divisors(a)
    ok = True
    for d in div:
        if d == a:
            if C[d] > 1:
                # log(C[d])
                ok = False
                break
        elif d in keys:
            ok = False
            break
    if ok:
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter
import sys

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

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i
        i += 1

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

checks = [False] * (1000009)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)
    elif not checks[a]:
        for j in range(a, 1000009, a):
            checks[j] = True

# log(B)

ans = 0

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
        for j in range(a, 1000009, a):
            checks[j] = True

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

S = raw_input()
T = raw_input()

CS = [S.count(s) for s in S]
TS = [T.count(t) for t in T]

if False in [CS[i] == TS[i] for i in range(len(CS))]:
	print 'No'
else:
	print 'Yes'


### FIXED CODE ###

S = raw_input()
T = raw_input()

CS = {}
for s in S:
	if s not in CS:
		CS[s] = 1
	else:
		CS[s] += 1
TS = {}
for t in T:
	if t not in TS:
		TS[t] = 1
	else:
		TS[t] += 1

if False in [CS[S[i]] == TS[T[i]] for i in range(len(T))]:
	print 'No'
else:
	print 'Yes'
### BUGGY CODE ###

n,k,q=map(int,input().split())
lists=[]
for i in range(q):
    s=int(input())
    lists.append(s)

for x in range(n):
    if lists.count(x+1)+k-q>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q=map(int,input().split())
lists=[0]*n
for i in range(q):
    a=int(input())
    lists[a-1]+=1
for i in range(n):
    check=k-(q-lists[i])
    if check>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

s = input()
l = len(s)

if l < 4:
    print(0)
    exit()

ans = 0
for i in range(0,l-3):
    temp = int(s[i])
    for j in range(i+1,l):
        temp = temp*10 + int(s[j])
        num = int(temp)
        if num%2019 == 0:
            ans += 1

print(ans)

### FIXED CODE ###

s = input()[::-1]
n = len(s)
amari = [0]*2019
amari[0] = 1

temp = 0
d = 1
for char in s:
    temp += int(char)*d
    temp %= 2019
    d *= 10
    d %= 2019  
    amari[temp] += 1

ans = 0
for i in amari:
    ans += i*(i-1)/2

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

s = input()[::-1]
n = len(s)
amari = [0]*2019
amari[0] = 1

temp = 0
d = 1
for char in s:
    temp += int(char)*d
    temp %= 2019
    amari[temp] += 1
    d *= 10

ans = 0
for i in amari:
    ans += i*(i-1)/2

print(int(ans))



### FIXED CODE ###

s = input()[::-1]
n = len(s)
amari = [0]*2019
amari[0] = 1

temp = 0
d = 1
for char in s:
    temp += int(char)*d
    temp %= 2019
    d *= 10
    d %= 2019  
    amari[temp] += 1

ans = 0
for i in amari:
    ans += i*(i-1)/2

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

N = int(input())
S = str(input())
RGB = [0] * 3
for i in range(N):
  if S[i] == "R":
    RGB[0] += 1
  elif S[i] == "G":
    RGB[1] += 1
  else:
    RGB[2] += 1
    
ans = RGB[0] * RGB[1] * RGB[2]

for i in range(1, 2000):
  for j in range(1, N + 1):
    if (j + 2 * i) <= N:
      if S[j - 1] != S[j + i - 1]:
        if S[j + 2 * i - 1] != S[j + i - 1]:
          if S[j - 1] != S[j + 2 * i - 1]:
            ans -= 1
            
print(max(ans, 0))
  


### FIXED CODE ###

N = int(input())
S = str(input())
R, G, B = 0, 0, 0
for i in range(N):
  if S[i] == "R":
    R += 1
  elif S[i] == "G":
    G += 1
  else:
    B += 1
    
ans = R * G * B 

for i in range(1, 2000):
  for j in range(1, N - 2 * i + 1):
    if S[j - 1] != S[j + i - 1]:
      if S[j + 2 * i - 1] != S[j + i - 1]:
        if S[j - 1] != S[j + 2 * i - 1]:
          ans -= 1
            
print(max(ans, 0))
### BUGGY CODE ###

#074_D
from copy import deepcopy
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]

def warshall_floyd(d, v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

b = deepcopy(a)
warshall_floyd(b, n)

flg = True
ans = 0
for i in range(n):
    for j in range(n):
        if b[i][j] < a[i][j]:
            flg = False
            break
        else:
            flg2 = True
            for k in range(n):
                if i == k or j == k:
                    continue
                elif b[i][j] == b[i][k] + b[k][j]:
                    flg2 = False
            ans += b[i][j] if flg2 else 0
                    
print(ans//2 if flg else -1)

### FIXED CODE ###

#074_D
from copy import deepcopy
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]

def warshall_floyd(d, v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

b = deepcopy(a)
warshall_floyd(b, n)

flg = True
ans = 0
for i in range(n):
    for j in range(n):
        if b[i][j] < a[i][j]:
            flg = False
            break
        else:
            flg2 = True
            for k in range(n):
                if i == k or j == k:
                    continue
                elif b[i][j] == b[i][k] + b[k][j]:
                    flg2 = False
            ans += b[i][j] if flg2 else 0
                    
print(ans//2 if flg else -1)
### BUGGY CODE ###

a=int(input())
b=7
for i in range(a):
  if b%a==0:
    print(i+1)
    break
  b=10*b+7
  if i==a-1:
    print(-1)
    break
  

### FIXED CODE ###

a=int(input())
b=7
for i in range(a):
  if b%a==0:
    print(i+1)
    break
  b=10*b%a+7
  if i==a-1:
    print(-1)
    break
### BUGGY CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

from itertools import accumulate
inf = 2 * 10**9
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(list(accumulate([c1==c2 for c1, c2 in zip(C1, C2)]))[::-1] + [0])
    Z2.append([])
    for j in range(1, H+1):
        Z1.append(list(accumulate([c1==c2 for c1, c2 in zip(C1, C2[j:])]))[::-1] + [0])
        Z2.append(list(accumulate([c1==c2 for c1, c2 in zip(C1[j:], C2)]))[::-1] + [0])
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + (Z1[j-k][k] if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
N=input()

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

SOSU=get_primenumber(10**6)

#素因数分解
def factorization(n):
    arr = []
    temp = n
    #for i in range(2, int(-(-n**0.5//1))+1):
    for i in SOSU:
        if int(-(-n**0.5//1))+1<i:
            break
        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


ans=1
for i in range(2,N+1):
    L=factorization(i)
    fi=1
    for x,y in L:
        fi*=(y+1)
    ans+=i*fi
print ans

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
N=input()
A=[ 2 for _ in range(N+1)]
A[0]=0
A[1]=1

for cur in range(2,N+1):
    for i in range(cur*2,N+1,cur):
        A[i]+=1

ans=0
for i in range(1,N+1):
    ans+=i*A[i]
print ans
### BUGGY CODE ###

q=int(input())
for i in range(q):   
    l,r=map(int,input().split())
    ans=0
    for j in range(l,r+1,2):
        k=(j+1)//2
        if j==1:
            continue
        if k==2:
            ans+=1
            continue
        flg=True
        for h in range(2,int(j**(1/2))+1):
            if j%h==0:
                flg=False
        for s in range(2,int(k**(1/2))+1):
            if k%s==0:
                flg=False
        if flg:
            ans+=1
    print(ans)

### FIXED CODE ###

import sys

Q = int(sys.stdin.readline().strip())
LR = []
for i in range(Q):
    LR.append([int(x) for x in sys.stdin.readline().strip().split()])

N = 10**5+1
Primes = list(range(N+1))
Primes[1] = 0

for p in Primes:
    if p * p > N+1: break
    if p == 0: continue
    for i in range(p + p, N+1, p):
        Primes[i] = 0

primes = [p for p in Primes if p > 0]

likes = []
r = 0
for n in range(N):
    if n%2 == 1 and Primes[n] > 0 and Primes[n//2+1] > 0:
        r += 1
    likes.append(r)

for i in range(Q):
    print(likes[LR[i][1]] - likes[LR[i][0]-1])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
from scipy.sparse.csgraph import dijkstra

def main():
    N = int(input())
    path = [[False] * N for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, readline().rstrip().split())
        path[u-1][v-1] = w
        path[v-1][u-1] = w
    
    G = dijkstra(path, indices=0)
    for i in range(N):
        if G[i] % 2 == 0:
            print(0)
        else:
            print(1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop

def dijkstra(path, N, a):
    visited = [False] * N
    que = [(0, a)]
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[a] = 0  # 始点aからaへの距離は0
    while que:
        d, v = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))

    return dist

def main():
    N = int(input())
    path = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, readline().rstrip().split())
        path[u-1].append((w, v-1))
        path[v-1].append((w, u-1))
    
    G = dijkstra(path, N, 0)
    for i in range(N):
        if G[i] % 2 == 0:
            print(0)
        else:
            print(1)

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

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

import numpy as np

def gcd(x: int, y: int):
  while(y!=0):
    tmp = x%y
    x = y
    y = tmp
  #if (y == 0):
  #  return x
  #else:
  #  return gcd(y, x%y)
  return x

g = 1
for i in range(N):
  g = g * A[i] // gcd(g, A[i])
an = 0
MOD = 10**9+7

for x in A:
  #print(g,g//x)
  an += g//x
  an %= MOD

print(an)


### FIXED CODE ###

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

#N = 10000
#A = [i*2+1 for i in range(1,N+1)]

MOD = 10**9+7

sm = 0
for x in A:
  sm += pow(x,MOD-2,MOD)
  sm %= MOD

def gcd(x: int, y: int):
  while(y!=0):
    tmp = x%y
    x = y
    y = tmp
  return x

g = 1
for i in range(N):
  g = g * A[i] // gcd(g, A[i]) #pow(gcd(g, A[i]), MOD-2, MOD)
  #print(g)

an = g * sm % MOD

'''
for x in A:
  #print(g,g//x)
  an += g*pow(x,MOD-2,MOD)
  an %= MOD
  print(g,g//x,an)
'''

print(an)
### BUGGY CODE ###

#problem C
import math
input_d31 = input()
K = int(input_d31)

gcd = 0

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            gcd1 = math.gcd(i,j)
            gcd2 = math.gcd(gcd1,k)
            gcd += gcd2
print(gcd)


### FIXED CODE ###

#problem C

import math

gcd = 0
gcd1 = 0
gcd2 = 0
gcd3 = 0

input_d31 = input()
K = int(input_d31)

gcd1 = sum(range(1,K+1))

for i in range(1,K+1):
    for j in range(i+1,K+1):
        gcd2 += math.gcd(i,j)
            
for i in range(1,K+1):
    for j in range(i+1,K+1):
        gcdd = math.gcd(i,j)
        for k in range(j+1,K+1):
            gcd3 += math.gcd(gcdd,k)
            
gcd = gcd1 + gcd2*6 + gcd3*6
            
print(gcd)
### BUGGY CODE ###

from math import factorial
pos = map(int, input().split())

x, y = sorted(pos)

num_twos = x // 2
rem = x % 2

solution = 0

m = 10**9 + 7 - 2


def ncr(n, r):
    return factorial(n) * factorial(r)**(m) * factorial(n-r)**(m)


while not (y == num_twos + (rem*2)):
    num_twos -= 1
    rem += 2

    if y < (num_twos + rem*2):
        print(0)
        exit()

solution = ncr(num_twos + rem, rem)

print(int(solution))


### FIXED CODE ###

from math import factorial
pos = map(int, input().split())
p = 10**9 + 7
x, y = sorted(pos)

if (x+y) % 3 != 0:
    print(0)
    exit()

n = (-x + 2 * y) // 3
m = (-y + 2 * x) // 3

# Python3 function to
# calculate nCr % p


def ncr(n, r, p):
    # initialize numerator
    # and denominator
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den,
                      p - 2, p)) % p


ans = ncr(n+m, n, p)
print(ans)
### BUGGY CODE ###

import math
K = int(input())
count = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            count += math.gcd(math.gcd(i,j),k)
print(count)

### FIXED CODE ###

import math
K = int(input())
count = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        temp = math.gcd(i,j)
        for k in range(1,K+1):
            count += math.gcd(temp,k)
print(count)
### BUGGY CODE ###

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

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

sum = 0
while len(n) > 1:
    sum += int(n.pop(0))


sum += int(n[0])
if sum % 9 == 0:
    print("Yes")
else:
    print("No")


# print("{}".format(ans))


### FIXED CODE ###

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

# Input#
n = list(input())
# n, k = map(int, input().split())
# a = list(map(int, input().split()))
sum = 0
for i in n:
    sum += int(i)

if sum % 9 == 0:
    print("Yes")
else:
    print("No")


# print("{}".format(ans))