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

import numpy as np

q = int(input())

# 素数列挙
n = 10**5 + 1
primes = set(range(2, n+1))

for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))

arr = np.array(list(primes))
arr = np.bincount(arr)

# 素数かつ2017に似た数を列挙
like_2017 = np.zeros(n, bool)
for i in np.where(arr == 1)[0]:
    if (i + 1) // 2 in primes:
        like_2017[i] = True


def cnt_primes(l, r):
    return like_2017[l:r + 1].sum()


ans = []
for _ in range(q):
    tmp = 0
    l, r = map(int, input().split())
    tmp += cnt_primes(l, r)
    ans.append(tmp)

print(*ans, sep="\n")

### FIXED CODE ###

import numpy as np

q = int(input())

# 素数列挙
n = 10**5 + 1
primes = set(range(3, n+1, 2))
for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)

arr = np.array(list(primes))
arr = np.bincount(arr)

# 素数かつ2017に似た数を列挙
like_2017 = np.zeros(n, bool)
for i in np.where(arr == 1)[0]:
    if (i + 1) // 2 in primes:
        like_2017[i] = True

like_2017 = like_2017.cumsum()


def cnt_primes(l, r):
    return like_2017[r] - like_2017[l - 1]


ans = []
for _ in range(q):
    tmp = 0
    l, r = map(int, input().split())
    tmp += cnt_primes(l, r)
    ans.append(tmp)

print(*ans, sep="\n")
### BUGGY CODE ###

from queue import Queue

n , q = map(int, input().split())
lab = []
points = [0]*n
for i in range(n-1):
    lab.append(list(map(int, input().split())))
lpx = []
for i in range(q):
    lpx.append(list(map(int, input().split())))

lll = []
for i in range(n):
    childs = Queue()
    inc = []
    parent = i+1
    childs.put(parent)
    while childs.qsize() > 0:
        a = childs.get()
        inc.append(a)
        for k in lab:
            if k[0] == a:
                childs.put(k[1])
    lll.append(list(set(inc)))

for i in lpx:
    for j in lll[i[0]-1]:
        points[j-1] += i[1]
print(' '.join(map(str, points)))


### FIXED CODE ###

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

N,Q = map(int,input().split())
aLst = [[int(x) for x in input().split()] for _ in range(N-1)]
pLst = [[int(x) for x in input().split()] for _ in range(Q)]

tmpLst = [[] for _ in range(N+1)]
for i, j in aLst:
    tmpLst[i].append(j)
    tmpLst[j].append(i)

ansLst = [0] * (N + 1)
for i,j in pLst:
    ansLst[i] += j

def dfs(v, p):
    for i in tmpLst[v]:
        if i == p:
            continue
        ansLst[i] += ansLst[v]
        dfs(i, v)


dfs(1, 0)

ans = ' '.join(map(str, ansLst[1:]))
print(ans)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n = int(input())
list_ABC = [ list(map(int,input().split(" "))) for i in range(n-1)]
q, k = map(int, input().split())
list_XY = [ list(map(int,input().split(" "))) for i in range(q)]

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, directed=True).astype(int)

for x, y in list_XY:
    print(b[x-1,k-1]+b[k-1,y-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

h, w = map(int, input().split())
s = [input() for _ in range(h)]

d = [[1, 0], [0, 1]]

ans = float("inf")


def dfs(hh, ww, c, cnt):
    if hh == h - 1 and ww == w - 1:
        global ans
        ans = min(ans, cnt)

    for dh, dw in d:
        nh = hh + dh
        nw = ww + dw
        if nh < h and nw < w:
            if c == "#":
                dfs(nh, nw, s[nh][nw], cnt)
            else:
                if s[nh][nw] == "#":
                    dfs(nh, nw, s[nh][nw], cnt + 1)
                else:
                    dfs(nh, nw, s[nh][nw], cnt)


dfs(0, 0, s[0][0], 0)
if s[0][0] == "#":
    ans += 1
print(ans)


### FIXED CODE ###

from math import ceil
from collections import defaultdict

h, w = map(int, input().split())
s = [input() for _ in range(h)]

n = h * w
INF = 100 * 100

dp = defaultdict(lambda: INF)
if s[0][0] == "#":
    dp[(1, 1, 1)] = 1
else:
    dp[(1, 1, 0)] = 0

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i-1][j-1] == "#":
            dp[(i, j, 1)] = min(dp[(i, j, 1)], dp[(i-1, j, 0)] + 1, dp[(i-1, j, 1)], dp[(i, j-1, 0)] + 1, dp[(i, j-1, 1)])
        else:
            dp[(i, j, 0)] = min(dp[(i, j, 0)], dp[(i-1, j, 0)], dp[(i-1, j, 1)] + 1, dp[(i, j-1, 0)], dp[(i, j-1, 1)] + 1)

idx = 1 if s[h-1][w-1] == "#" else 0
ans = dp[(h, w, idx)]
ans = ceil(ans / 2)
print(ans)
### BUGGY CODE ###

import itertools

n = int(input())
lis = list(input())

ans = list(itertools.combinations(lis, 3))
print(len(set(ans)))


### FIXED CODE ###

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

dp1 = [[0 for i in range(10)] for _ in range(n + 1)]
dp2 = [[0 for i in range(100)] for _ in range(n + 1)]
dp3 = [[0 for i in range(1000)] for _ in range(n + 1)]

for i in range(n):
    dp1[i + 1][int(s[i])] = 1
    for j in range(10):
        if dp1[i][j]:
            dp2[i + 1][j * 10 + int(s[i])] = 1
            dp1[i + 1][j] = 1
    for j in range(100):
        if dp2[i][j]:
            dp3[i + 1][j * 10 + int(s[i])] = 1
            dp2[i + 1][j] = 1
    for j in range(1000):
        if dp3[i][j]:
            dp3[i + 1][j] = 1

print(sum(dp3[n]))
### BUGGY CODE ###

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

isDiff = True

for i in range(n) :

    for j in range(n) :
        if i == j :
            continue

        if a[i] == a[j] :
            isDiff = False
            break

if isDiff :
    print('YES')
else :
    print('NO')


### FIXED CODE ###

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

aa = set(a)

if len(a) == len(aa) :
    print('YES')
else :
    print('NO')
### BUGGY CODE ###

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

import itertools

cnt = 0
for n in range(1, N+1):
    for i in itertools.combinations(x, n):
        if sum(i) / n == A:
            cnt += 1
print(cnt)

### FIXED CODE ###

N, A = input().split(" ")
N, A = int(N), int(A)
x = input().split(" ")
x = [int(i) for i in x]
y = [0]+[int(i)-A for i in x]
X = max(x+[A])

dp = [[0 for t in range(2*N*X+1)] for j in range(N+1)]

for j in range(N+1):
    for t in range(2*N*X+1):
        if j == 0 and t == N*X:  # 0枚の時は0しか達成できない
            dp[j][t] = 1
        elif j >= 1 and (t - y[j-1] < 0 or t-y[j] > 2*N*X):  # xの値が平均Aを超えてしまう場合は、前回の結果から場合の総数に変化なし
            dp[j][t] = dp[j-1][t]
        elif j >= 1 and 0 <= t-y[j-1] <= 2*N*X:  # 前回の場合の総数に、今回の数を足して0になる場合の総数を足す
            dp[j][t] = dp[j-1][t] + dp[j-1][t-y[j]]
        else:
            dp[j][t] = 0
print(dp[N][N*X] - 1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
  print(a.count(i+1))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
buka=[0]*n
for i in a:
  buka[i-1]+=1

for b in buka:
  print(b)
### BUGGY CODE ###

#E問題
import bisect

N = int(input())
A = [int(input()) for i in range(N)]
B = []
for i in range(N):
    if len(B) == 0:
        B.append(A[i])
    else:
        if B[0] >= A[i]:
            B.append(A[i])
        else:
            index = bisect.bisect_left(B,A[i])-1
            B[index] = A[i]
    B.sort()
print(len(B))

### FIXED CODE ###

#E問題
import heapq
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
A = A[::-1]

C = []
for i in range(N):
    if i == 0:
        C.append(A[i])
    else:
        li = bisect.bisect_right(C,A[i])
        if li == len(C):
            C.append(A[i])
        else:
            C[li] = A[i]
    
print(len(C))
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd,numbers)

K=int(input())
count=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            count+=gcd(a,b,c)
print(count)

### FIXED CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd,numbers)

K=int(input())
count=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            count+=gcd(a,b,c)
print(count)
### BUGGY CODE ###

from bisect import bisect
from collections import defaultdict
def main():
	n, k = map(int, input().split())
	*a, = map(int, input().split())
	idx = defaultdict(list)
	for i, x in enumerate(a):
		idx[x].append(i)
	m = (k * n).bit_length()
	dub = [[-1] * n for _ in range(m)]
	for i, x in enumerate(a):
		if i == idx[x][-1]:
			dub[0][i] = n + idx[x][0] - i
		else:
			dub[0][i] = idx[x][bisect(idx[x], i)] - i
	# print(dub[0])
	for i in range(m - 1):
		for j in range(n):
			if dub[i][j]<n*k and dub[i][j]!=-1:
				dub[i + 1][j] = dub[i][j] + 1 + dub[i][(j + dub[i][j] + 1) % n]
	# print(dub)
	now = -1
	for i in range(m - 1, -1, -1):
		if dub[i][(now+1)%n]!=-1 and now + 1 + dub[i][(now + 1) % n] < n * k:
			now += 1 + dub[i][(now + 1) % n]
	# print(now)
	if now == n * k:
		print("")
		exit()
	b = a[(now + 1) % n:]
	# print(b)
	inQ = {x: False for x in b}
	Q = []
	for x in b:
		if inQ[x]:
			while Q[-1] != x:
				inQ[Q.pop()] = False
			Q.pop()
			inQ[x] = False
		else:
			inQ[x] = True
			Q.append(x)
	print(" ".join(map(str, Q)))

if __name__ == '__main__':
	main()


### FIXED CODE ###

from bisect import bisect
from collections import defaultdict
def main():
	n, k = map(int, input().split())
	*a, = map(int, input().split())
	idx = defaultdict(list)
	for i, x in enumerate(a):
		idx[x].append(i)
	m = (k * n).bit_length()
	dub = [[-1] * n for _ in range(m)]
	for i, x in enumerate(a):
		if i == idx[x][-1]:
			dub[0][i] = n + idx[x][0] - i
		else:
			dub[0][i] = idx[x][bisect(idx[x], i)] - i
	# print(dub[0])
	for i in range(m - 1):
		for j in range(n):
			if dub[i][j]<n*k and dub[i][j]!=-1:
				dub[i + 1][j] = dub[i][j] + 1 + dub[i][(j + dub[i][j] + 1) % n]
	# print(dub)
	now = -1
	for i in range(m - 1, -1, -1):
		if dub[i][(now+1)%n]!=-1 and now + 1 + dub[i][(now + 1) % n] < n * k:
			now += 1 + dub[i][(now + 1) % n]
	# print(now)
	if now == n * k:
		print("")
		exit()
	b = a[(now + 1) % n:]
	# print(b)
	inQ = {x: False for x in b}
	Q = []
	for x in b:
		if inQ[x]:
			while Q[-1] != x:
				inQ[Q.pop()] = False
			Q.pop()
			inQ[x] = False
		else:
			inQ[x] = True
			Q.append(x)
	print(" ".join(map(str, Q)))

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

n = int(input())
A = list(map(int,input().split()))
B = sorted(set(A))
dic = {}
ans = 0

for i in range(len(B)):
    if A.count(B[i]) > 1:
        C = A.count(B[i])
        dic[B[i]] = C
        ans += C*(C-1)//2
    else:
        dic[B[i]] = 1
        
for i in range(n):
    x = dic[A[i]]
    print(ans - x*(x-1)//2 + (x-1)*(x-2)//2)

### FIXED CODE ###

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

import collections
c = collections.Counter(a)

for i in c.values():
    ans += i*(i-1)//2
    
for i in a:
    print(ans - c[i])
### BUGGY CODE ###

S = input()
L = len(S)
S = int(S)
ans = 0
for i in range(L,3,-1):
    for j in range(i-4,-1,-1):
        if S%(10**i)%2019 == S%(10**j)%2019:
            ans += 1
print(ans)

### FIXED CODE ###

# import sys 
# import os
# path = os.path.join(os.getcwd(),'input.txt')
# input = open(path).readline

import numpy as np
S = input()
cand = np.zeros(2019,dtype=int)
rem = 0
order = 1
mod = 2019
for s in S[::-1]:
    rem += (int(s)*order)%mod
    rem %= mod
    cand[rem] +=1
    order *= 10
    order %=mod
ans = cand[0]
cand = cand[cand>1]
for c in cand:
    ans += c*(c-1)/2
print(int(ans))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
cnt = 0
for i in range(n):
    for j in range(2, n-i):
        if a[i] + a[i+j] == j:
            cnt += 1
print(cnt)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = [int(i) for i in input().split()]
l_i = [a[i] + i + 1 for i in range(len(a))]
r_j = [i - a[i] + 1 for i in range(len(a))]
dl = defaultdict(int)
dr = defaultdict(int)
for i in range(n):
    dl[l_i[i]] += 1
    dr[r_j[i]] += 1

ans = 0
for i in dl.keys():
    ans += dl[i] * dr[i]

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

import itertools

def primes(n):
    l = []
    i = 2
    while i <= n**(1/2):
        while n % i == 0:
            n //= i
            l.append(i)
        i += 1
    if n > 1:
        l.append(n)
    return l

def mul(l):
    result = 1
    for i in l:
        result *= i
    return result

n = int(input())

prime_list = primes(n)

i,j = 1,n
for m in range(len(prime_list)):
    cmb = list(set(itertools.combinations(primes(n), m)))
    for c in cmb:
        s = mul(c)
        t = n//s
        if abs(s-t) < abs(i-j):
            i,j = s,t

print(i+j-2)


### FIXED CODE ###

import math

N = int(input())

ans = 10**15
for k in range(1, int(math.sqrt(N))+1):
    if N % k > 0:
        continue
    ans = min(ans, k + N//k - 2)
print(ans)
### BUGGY CODE ###

from functools import reduce
N, K = map(int, input().split())

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

before = reduce(lambda a, b: a * b, A[:K])
for i in range(1, N - K + 1):
    temp = reduce(lambda a, b: a * b, A[i:i + K])
    if temp > before:
        print("Yes")
    else:
        print("No")
    before = temp

### FIXED CODE ###

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

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

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

N,W = map(int,input().split())
dp = [0]*(W+1)
for i in range(N):
    w,v = map(int,input().split())
    for j in range(W-w+1)[::-1]:
        dp[j+w] = max(dp[j+w],dp[j] + v)
print(max(dp))


### FIXED CODE ###

N,W = map(int,input().split())
dp = [0]*(W+1)
for i in range(N):
    w,v = map(int,input().split())
    for j in range(W-w+1)[::-1]:
        dp[j+w] = max(dp[j+w],dp[j] + v)
print(max(dp))
### BUGGY CODE ###

import sys
import itertools
N = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
AK = []
for k in range(0, len(A)):
    AK.append(sorted([a for i,a in enumerate(A) if k != i]))
count = {}
for i,ak in enumerate(AK):
    n = AK.index(ak)
    if n != i:
        print(count[n])
        continue
    count[i] = 0
    for j in itertools.combinations(ak, 2):
        if j[0] == j[1]:
            count[i] += 1
    print(count[i])


### FIXED CODE ###

import sys
from collections import Counter

def choose(k, r):
    return k*(k-1) // r*(r-1)

N = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))

C = Counter(A)

ANS = sum([choose(v, 2) for v in C.values()])

for k in A:
    v = C[k]
    print(ANS
          - choose(v, 2)
          + choose(v-1, 2)
         )
### BUGGY CODE ###

N=int(input())
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
  s=input()
  d[s]+=1
x=max(d.values())
max_k_list=[]
while len(d)>0 and max(d.values())==x:
  max_k_list.append(max(d, key=d.get))
  del d[max_k_list[-1]]
max_k_list.sort()
for a in max_k_list:
  print(a)

### FIXED CODE ###

N=int(input())
S = [input() for i in range(N)]
S.sort()
import itertools
gr = itertools.groupby(S)
ans=[]
n=0
for key, group in gr:
  a=len(list(group))
  if a>n:
    ans=[]
    n=a
    ans.append(key)
  elif a==n:
    ans.append(key)
for a in ans:
  print(a)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K == 1:
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    for j in d[1]:
        d[j].remove(1)
    ans = K * perm(K - 1, len(d[1]))
    root = d[1]
    a = K - 2
    while True:
        children = []
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= perm(a, b)
            ans %= 1000000007
            children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break


### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
### BUGGY CODE ###

import sys
import time

class Node:
    def __init__(self, key = None):
        self.key = key
        self.left = None
        self.right = None

def insert(key):
    global root
    z = Node(key)
    y = None
    x = root
    while x:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right

    if y is None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def inorderTreeWalk(node):
    if node:
        return inorderTreeWalk(node.left) + " " + str(node.key) + inorderTreeWalk(node.right)
    return ""

def preorderTreeWalk(node):
    if node:
        return " " + str(node.key) + preorderTreeWalk(node.left) + preorderTreeWalk(node.right)
    return ""

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "i":
            insert(int(line.split()[1]))
        else:
            print inorderTreeWalk(root)
            print preorderTreeWalk(root)

### FIXED CODE ###

import sys

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

def insert(z):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def inorderTreeWalk(node):
    global In
    if node:
        inorderTreeWalk(node.left)
        In.append(str(node.key))
        inorderTreeWalk(node.right)

def preorderTreeWalk(node):
    global Pre
    if node:
        Pre.append(str(node.key))
        preorderTreeWalk(node.left)
        preorderTreeWalk(node.right)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "i":
            insert(Node(int(line.split()[1])))
        else:
            In = []
            Pre = []
            inorderTreeWalk(root)
            print " " + " ".join(map(str, In))
            preorderTreeWalk(root)
            print " " + " ".join(map(str, Pre))
### BUGGY CODE ###

import numpy as np
NM = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
AB=[]
for i in range(NM[1]):
  AB.append([int(x) for x in input().split()])
X=np.ones(NM[0])
n=0
x=0
for i in range(NM[0]):
  if X[i]==0:
    continue
  for j1 in AB:
    for j2 in j1:
      if j2==i+1:
        if j1.index(j2)==0:
          n=j1[1]
        else:
          n=j1[0]
        if H[i]<=H[n-1]:
          X[i]=0
          #break
        else:
          X[n-1]=0
  if X[i]==1:
    x+=1
print(x)

"""
6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

3
"""

### FIXED CODE ###

import numpy as np
NM = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
X=np.ones(NM[0])
AB=[]
for i in range(NM[1]):
  AB.append([int(x) for x in input().split()])
  if H[AB[i][0]-1]>H[AB[i][1]-1]:
    X[AB[i][1]-1]=0
  elif H[AB[i][0]-1]<H[AB[i][1]-1]:
    X[AB[i][0]-1]=0
  else:
    X[AB[i][1]-1]=0
    X[AB[i][0]-1]=0
x=0
for i in range(NM[0]):
  if X[i]==1:
    x+=1
print(x)

"""
6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

3
"""
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, mod = 10**5+2, 10**9+7
def extGcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = extGcd(b, a % b)
        x -= (a // b) * y
        return d, y, x
def modInv(a):
    return extGcd(a, mod)[1] % mod
fac = [1] + [None] * N
for i in range(1, N+1):
    fac[i] = i * fac[i-1] % mod
facInv = [1] + [None] * N
for i in range(1, N+1):
    facInv[i] = modInv(fac[i])
def modCom(n, k):
    return 0 if n < k else fac[n] * pow(fac[k],mod-2,mod) * pow(fac[n-k],mod-2,mod) % mod
n = int(input())
a = list(map(int, input().split()))
for x in range(1, n+1):
    if a.count(x) == 2: break
fi = a.index(x) + 1
si = a[fi:].index(x) + fi + 1
print(n)
for k in range(2, n+1):
    print((modCom(n+1, k) - modCom(fi+n-si, k-1)) % mod)
print(1)


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N, mod = 10**5+1, 10**9+7
fac = [1, 1] + [None] * N
inv = [0, 1] + [None] * N
facInv = [1, 1] + [None] * N
for i in range(2, N+1):
    fac[i] = i*fac[i-1]%mod
    inv[i] = mod-(inv[mod%i]*(mod//i))%mod
    facInv[i] = facInv[i-1]*inv[i]%mod
def modCom(n, k):
    return 0 if n < k else fac[n] * facInv[k] * facInv[n-k] % mod
n = int(input())
a = list(map(int, input().split()))
dic = defaultdict(int)
for i, x in enumerate(a):
    if dic[x] > 0:
        fi = dic[x]
        si = i+1
        break
    dic[x] = i+1
print(n)
for k in range(2, n+1):
    print((modCom(n+1, k) - modCom(fi+n-si, k-1)) % mod)
print(1)
### BUGGY CODE ###

import sys
n,m=map(int,input().split())
s=input()
t=input()

def gcd(a, b):

	while b>0:

		a, b = b, a % b

	return a

def lcm(a, b):

	return a * b // gcd (a, b)


l=(lcm(n,m))

a=["A" for i in range(l)]

for i in range(n):
    a[int(l/n)*i]=s[i]

for i in range(m):
    if a[int(l/m)*i]!="A" and a[int(l/m)*i]!=t[i]:
        print(-1)
        sys.exit()
    
print(l)


### FIXED CODE ###

n,m=map(int,input().split())
s=input()
t=input()

#最大公約数
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

#最小公倍数
def lcm(x,y):
    return x*y//gcd(x,y)

l=lcm(n,m)

a=l//n
b=l//m
ln=[]
lm=[]
i=0
while i<n:
    ln.append(i)
    i+=b
i=0
while i<m:
    lm.append(i)
    i+=a

p=0
for i in range(len(ln)):
    if s[ln[i]]!=t[lm[i]]:
        p=1
if p==0:
    print(l)
else:
    print(-1)