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

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    tmp = bin(a)[2:]
    ret_r = [0] * n
    for i, t in enumerate(tmp[::-1]):
        ret_r[i] = int(t)
    return ret_r


def calc_sum(a, n_1_ls, n_1_max):
    '''
    aはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    a_binary = ret_binary(a)
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += ((2**i) * n_1) % MOD
        else:
            ret += ((2**i) * (n_1_max - n_1)) % MOD
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
for i in range(N - 2, -1, -1):
    a = A[i]
    a_pre = A[i + 1]
    n_1_ls = add_koko(n_1_ls, ret_binary(a_pre))
    n_1_max += 1
    tmp = calc_sum(a, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD

print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return ret_r


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
for a in A:
    tmp = ret_binary(a)
    for i in range(n):
        n_1_ls[i] += tmp[i]


for i, n_1 in enumerate(n_1_ls):
    num_sonoketa = n_1 * (N - n_1)
    ans += (((2**i) % MOD) * num_sonoketa)
    ans %= MOD
print(ans)
### BUGGY CODE ###

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

sum_value = 0
for i in range(n-1):
    for j in range(i+1,n):
        sum_value += nums[i]*nums[j]

print(sum_value%1000000007)


### FIXED CODE ###

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

mod = 1000000007


ans = 0
n = A[0]
for a in A[1:]:
    ans += a * n
    n += a

print(ans%mod)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 
import numpy as np

def resolve():
    N, W = map(int, input().split())
    w = [0] * N
    v = [0] * N
    for i in range(N):
        w[i], v[i] = map(int, input().split()) 

    sum_v = sum(v)

    # dp[i][j]: 0〜(i-1)まで使ったときの価値jのときの重みの総和の最小値
    dp = [[np.inf]*(sum_v+1) for i in range(N+1)]
    dp[0][0] = 0

    for i in range(1, N+1):
        for j in range(sum_v+1):
            if j-v[i-1] >= 0:
                dp[i][j] = min(dp[i-1][j-v[i-1]] + w[i-1], dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

    print(max([i for i, w in enumerate(dp[N]) if w<=W]))

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N, W = map(int, input().split())
    w = [0] * N
    v = [0] * N
    for i in range(N):
        w[i], v[i] = map(int, input().split()) 

    sum_v = sum(v)

    # dp[i][j]: 0〜(i-1)まで使ったときの価値jのときの重みの総和の最小値
    dp = [[sum(w)]*(sum_v+1) for i in range(N+1)]
    dp[0][0] = 0

    for i in range(1, N+1):
        for j in range(sum_v+1):
            if j-v[i-1] >= 0:
                dp[i][j] = min(dp[i-1][j-v[i-1]] + w[i-1], dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

    print(max([i for i, w in enumerate(dp[N]) if w<=W]))

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

def main():
    N, K = map(int, input().split())
    pN = list(map(lambda s: int(s) + 1, input().split()))

    ans = 0
    for i in range(N + 1 - K):
        ans = max(ans, sum(pN[i:i + K]) / 2)

    print(ans)


main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())

    pN_ = []

    ans = 0
    total = 0
    for i, s in enumerate(input().split()):
        total += 1 + int(s)
        pN_.append(total)

        if i == K - 1:
            ans = max(ans, (total / 2))
        elif K <= i:
            ans = max(ans, (total - pN_[i - K]) / 2)

    print(ans)


main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input())
    S = input().rstrip()
    tmp = set()
    ans = 0
    for index, i in enumerate(range(N-2)):
        for j in range(index+1, N-1):
            if S[i] + S[j] not in tmp:
                tmp.add(S[i] + S[j])
                ans += len(set(list(S[j + 1:])))
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input())
    S = input().rstrip()
    ans = 0
    for i in range(1000):
        i = str(i).zfill(3)
        prev = -1
        for s in i:
            pos = S.find(s, prev + 1)
            if pos > prev:
                prev = pos
            else:
                break
        else:
            ans += 1
    print(ans)


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

from queue import Queue

'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N = int(input())
q = Queue()
c = [0 for i in range(N)]
l = [0 for i in range(N)]

u, v, w = map(int,input().split())
c[u-1] = 1
l[u-1] = 0
c[v-1] = 1
l[v-1] = w
		
for i in range(1,N-1):
	u, v, w = map(int,input().split())
	u = u - 1
	v = v - 1
	if c[u] == 0 and c[v] == 0:
		q.put([u,v,w])
	elif c[u] == 0 and c[v] == 1:
		c[u] = 1
		l[u] = l[v] + w
	elif c[u] == 1 and c[v] == 0:
		c[v] = 1
		l[v] = l[u] + w

while not q.empty():
	u, v, w = q.get()
	if c[u] == 0 and c[v] == 0:
		q.put([u,v,w])
	elif c[u] == 0 and c[v] == 1:
		c[u] = 1
		l[u] = l[v] + w
	elif c[u] == 1 and c[v] == 0:
		c[v] = 1
		l[v] = l[u] + w

for i in l:
	print('{}'.format(i%2))

### FIXED CODE ###

N = int(input())
q = []
c = [0 for i in range(N)]
l = [0 for i in range(N)]
A = [[] for i in range(N)]
W = [[] for i in range(N)]

for i in range(N-1):
	u, v, w = map(int,input().split())
	u = u - 1
	v = v - 1
	
	A[u].append(v)
	A[v].append(u)
	W[u].append(w)
	W[v].append(w)

q.append(0)
while len(q):
	i = q.pop(0)
	c[i] = 1
	k = 0
	for j in A[i]:
		if c[j] == 0:
			q.append(j)
			l[j] = l[i] + W[i][k]
		k = k + 1

for i in l:
	print('{}'.format(i%2))
### BUGGY CODE ###

n=int(input())
ab=[]
p=[-1 for i in range(n+1)]
edge={}
G=[[] for i in range(n+1)]
used=[0 for i in range(n+1)]
for i in range(n-1):
    ab.append(list(map(int,input().split())))
    G[ab[i][0]].append(ab[i][1])
    G[ab[i][1]].append(ab[i][0])

max_n=0

for i in range(n+1):
    tmp=len(G[i])
    if tmp>max_n:
        max_n=tmp
        top=i

queue=[]
queue.append(top)

while len(queue)>0:
    num=queue.pop(0)
    used[num]=1
    color=1
    for i in range(len(G[num])):
        if used[G[num][i]]==0:
            if p[num]==color:
                color+=1
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            else:
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            color+=1

print(max_n)
for i in range(n-1):

    print(edge["{},{}".format(ab[i][0],ab[i][1])])

        




### FIXED CODE ###

n=int(input())
ab=[]
p=[-1 for i in range(n+1)]
edge={}
G=[[] for i in range(n+1)]
used=[0 for i in range(n+1)]
for i in range(n-1):
    ab.append(list(map(int,input().split())))
    G[ab[i][0]].append(ab[i][1])
    G[ab[i][1]].append(ab[i][0])

max_n=0

for i in range(n+1):
    tmp=len(G[i])
    if tmp>max_n:
        max_n=tmp
        top=i

queue=[]
queue.append(top)

while len(queue)>0:
    num=queue.pop(0)
    used[num]=1
    color=1
    for i in range(len(G[num])):
        if used[G[num][i]]==0:
            if p[num]==color:
                color+=1
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            else:
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            color+=1

print(max_n)
for i in range(n-1):

    print(edge["{},{}".format(ab[i][0],ab[i][1])])
### BUGGY CODE ###

L, R = map(int, input().split())

res = 1000000007

for i in range(L, R + 1):
    a = i % 2019
    for j in range(i + 1, R + 1):
        b = j % 2019
        res = min(res, a * b % 2019)

print(res)

### FIXED CODE ###

L, R = map(int, input().split())

res = 1000000007

if R - L + 1 > 2019:
    print(0)
else:
    amari = [i % 2019 for i in range(L, R + 1)]
    l = len(amari)
    for i in range(l):
        a = amari[i]
        for j in range(i + 1, l):
            b = amari[j]
            res = min(res, a * b % 2019)

    print(res)
### BUGGY CODE ###

N=int(input())
a=[int(input()) for _ in range(N)]

x=dict(zip(range(1,N+1),a))

route=[1,]
while 2 not in route:
  #print(x[route[-1]])
  if x[route[-1]] not in route:
    route.append(x[route[-1]])
  else:
    print(-1)
    exit()
print(len(route)-1)

### FIXED CODE ###

N=int(input())
x=[int(input()) for _ in range(N)]

on=1
ans=0
for _ in range(N):
  on=x[on-1]
  ans=ans+1
  if on==2:
    print(ans)
    exit()
  
print(-1)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort(reverse=True)
count = 0

for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1, n):
            if l[i] < l[j] + l[k]:
                count += 1
print(count)


### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int,input().split()))
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        short_2hen = l[i] + l[j]
        bis = bisect.bisect_left(l, short_2hen)
        count += bis - j - 1
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 20:57:47 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

x = 2019
S = list(input())
l = len(S)

a, b = [],[0]
s = ''
S.reverse()
for i in range(l):
#    a.append(int(S[:i+1]) % x)
#    if S[i] != '0':
    s = S[i] + s
    b.append(int(s) % x)

ans = 0

xx = [0 for _ in range(2019)]
for i in range(len(b)):
    xx[b[i]] += 1

def a(n):
    return n*(n+1)//2 

for i in range(len(xx)):
    if xx[i] > 1:
        ans += a(xx[i] - 1)

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 20:57:47 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 2019

S = input()
l = len(S)
#S = int(S)

a, b = [],[0]
s = 0
xx = [0 for _ in range(2019)]
xx[0] += 1
for i in range(l):
    s += int(S[-i-1])*pow(10,i,mod)
    s %= mod
#    b.append(s % x)
    xx[s] += 1

ans = 0
#for i in range(len(b)):
#    xx[b[i]] += 1
def a(n):
    return n*(n+1)//2 

for i in range(len(xx)):
    if xx[i] > 1:
        ans += a(xx[i] - 1)

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

import sys
n,m=map(int,input().split())
INF=10**15
d={}
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d.setdefault(a,[]).append(b)
  d.setdefault(b,[]).append(a)
dist=[INF for i in range(n)]
dist[0]=0
queue=[]
for i in d[0]:
  queue.insert(0,i)
  dist[i]=1

while(len(queue)):
  x=queue.pop()
  for i in d[x]:
    if(dist[i]==INF):
      queue.insert(0,i)
      dist[i]=dist[x]+1
if(dist[-1]==2):print("POSSIBLE")
else:print("IMPOSSIBLE")

### FIXED CODE ###

import sys
n,m=map(int,input().split())
INF=10**15
li1=set()
lin=set()
for i in range(m):
  a,b=map(int,input().split())
  if(a==1):li1.add(b)
  elif(b==1):li1.add(a)
  elif(a==n):lin.add(b)
  elif(b==n):lin.add(a)
for i in li1:
  if(i in lin):
    print("POSSIBLE")
    sys.exit()
    
print("IMPOSSIBLE")
### BUGGY CODE ###

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

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


### FIXED CODE ###

def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = map(int, input().split())
print(nap(n, cap))
### BUGGY CODE ###

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

set_a  = set(A)
count_l = []
for a in set_a:
    count_l.append(A.count(a))
 
s = 0
for c in count_l:
    s += c*(c-1)/2

ans = 0
for a in A:
    n = A.count(a)
    ans = s - n*(n-1)/2 + (n-1)*(n-2)/2
    print(int(ans))

### FIXED CODE ###

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

from collections import Counter
count = Counter(A)
 
s = 0
for c in list(count.values()):
    s += c*(c-1)/2

ans = 0
for a in A:
    n = count[a]
    ans = s - n*(n-1)/2 + (n-1)*(n-2)/2
    print(int(ans))
### BUGGY CODE ###

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

import re

S = input()

s = S
ans = 0
while 1:
    s, t = re.subn("01|10", "", s)
    ans += t * 2
    if t == 0:
        break

print(ans)


### FIXED CODE ###

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

S = input()

ans = min(S.count('0'), S.count('1'))
print(ans*2)
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                ans += 1
                
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())

ans = 0

for x in range(k + 1):
    for y in range(k + 1):
        z = s - (x + y)
        if 0 <= z <= k:
            ans += 1
print(ans)
### BUGGY CODE ###


import sys

sys.setrecursionlimit(100000)

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)


k = int(input())

x = 0

for a in range(1, k+1):
    for b in range(1, k+1):
        q = gcd(b, a)
        for c in range(1, k+1):
            x += gcd(q, c)

print(x)


### FIXED CODE ###

from math import gcd


k = int(input())

ans = 0

gcd_sum = [0] * 201

for i in range(1, k+1):
    for j in range(1, k+1):
        gcd_sum[i] += gcd(i, j)

for a in range(1, k+1):
    for b in range(1, k+1):
        q = gcd(a, b)
        ans += gcd_sum[q]

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

n,k = map(int, input().split())
ps = list(map(int, input().split()))
ans = 0
max_ps = 0
start = 0

for i in range(n):
    if max_ps <= sum(ps[i:i+k]):
        start = i
        max_ps = sum(ps[i:i+k])

print(sum([sum(range(i+1))/i for i in ps[start:start+k]]))

### FIXED CODE ###

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

tmp = sum(ps[:k])
max_ps = tmp
start = 0

for i in range(1,n-k+1):
    tmp = tmp-ps[i-1]+ps[i+k-1]
    if tmp >= max_ps:
        max_ps = tmp
        start = i

print(sum([(i*(i+1))/ (2*i) for i in ps[start:start+k]]))
### BUGGY CODE ###

n = int(input())
L = list(map(int,input().split()))
L.sort(reverse=True)
ans = 0
for i in range(n-2):
    tmp = 0
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            a, b, c = L[i], L[j], L[k]
            if a < b + c and b < a + c and c < a + b:
                ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
L = list(map(int,input().split()))
L.sort()
L2 = []
ans = 0
import bisect
for i in range(n-2):
    for j in range(i+1, n-1):
        index = bisect.bisect_left(L,  L[i] + L[j])
        ans += index - j - 1
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
count = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] != S[j]:
            for k in range(j+1, N):
                if j - i != k - j and S[i] != S[k] and S[j] != S[k]:
                    count += 1

print(count)


### FIXED CODE ###

N = int(input())
S = input()
count = 0
R = S.count("R")
G = S.count("G")
B = S.count("B")
count = R*G*B

for i in range(N-2):
    for j in range(i+1, N-1):
        if j +(j-i) <= N-1 and S[i] != S[j]:
            if S[i] != S[j+(j-i)] and S[j] != S[j+(j-i)]:
                count -= 1

print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

SCORE=dict()

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番
    #print(i,j,k,l)
    
    if SCORE.get((i,j))!=None:
        return SCORE.get((i,j))+k
    if i==j:
        SCORE[(i,j)]=0
        return k

        

    if l==1:
        SCORE[(i,j)]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[(i,j)]+k
    if l==-1:
        SCORE[(i,j)]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[(i,j)]+k



hand=N%2
for i in range(N+1):
    for j in range(N-i+1):
        score(j,j+i,0,(-1)**(j+j+i+hand))

print(SCORE[(0,N)])

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番
    #print(i,j,k,l)
    
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k
    if i==j:
        SCORE[i][j]=0
        return k

        

    if l==1:
        SCORE[i][j]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[i][j]+k
    if l==-1:
        SCORE[i][j]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[i][j]+k



hand=N%2
for i in range(N+1):
    for j in range(N-i+1):
        score(j,j+i,0,(-1)**(j+j+i+hand))

print(SCORE[0][N])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
s = input()


inf=float("inf")
#i番目のマスに行くための最小手数と、その出目
from copy import copy
dp = [(0,[])] + [(inf,None) for _ in range(n)]
for i in range(1,n+1):
    if s[i]=="0":
        for j in range(m,0,-1):
            if i-j<0:
                continue
            if dp[i-j][0]<inf:
                dp[i]=(dp[i-j][0]+1,dp[i-j][1]+[j])
                break
if dp[-1][1]:

    print(" ".join(map(str,dp[-1][1])))
else:
    print(-1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
s = input()


inf=float("inf")
#i番目のマスに行くための最小手数と、なんマス移動してきたか
dp = [(0,0)] + [(inf,None) for _ in range(n)]
for i in range(1,n+1):
    if s[i]=="0":
        for j in range(min(m,i),0,-1):
            if dp[i-j][0]<inf:
                dp[i]=(dp[i-j][0]+1,j)
                break
if dp[-1][1]:
    i = n
    ret = []
    ra = ret.append
    while dp[i][1]:
        ra(dp[i][1])
        i-=dp[i][1]
    print(" ".join(map(str,ret[::-1])))
else:
    print(-1)
### BUGGY CODE ###

n,k=map(int,raw_input().split())
if n%k==0:
    print 0
    quit()
tmp=10**18+1
while tmp>=n:
    tmp=n
    n=abs(n-k)
print tmp

### FIXED CODE ###

n,k=map(int,raw_input().split())
print min(n%k,abs(k-n%k))
### BUGGY CODE ###

import sys
from collections import Counter
from functools import lru_cache

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


factorials = get_factorials(N + 1, MOD)


@lru_cache(maxsize=None)
def inv(a, mod):
    """
    a の逆元
    :param a:
    :return:
    """
    return pow(a, mod - 2, mod)


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0
    r = min(n - r, r)
    return factorials[n] * inv(factorials[r], mod) * inv(factorials[n - r], mod) % mod


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

# dup より端から i 個選ぶ組み合わせ
sides = [ncr(L + N - r, i, MOD) for i in range(N + 2)]

# 全部選んで選びすぎを引く
# dup を 1 つ選び、その他を dup より端から選ぶ組み合わせが重複する
ans = [(ncr(N + 1, k, MOD) - sides[k - 1]) % MOD for k in range(1, N + 2)]

print('\n'.join(map(str, ans)))


### FIXED CODE ###

import sys
from collections import Counter

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def mod_invs(max, mod):
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def get_ncrs(n):
    invs = mod_invs(N + 1, MOD)
    ret = [1]
    ncr = 1
    for i in range(1, n + 1):
        ncr = ((ncr * (n - i + 1) % MOD) * invs[i]) % MOD
        ret.append(ncr)
    return ret


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

# dup より端から i 個選ぶ組み合わせ
side_ncrs = get_ncrs(L + N - r)
while len(side_ncrs) < N + 2:
    side_ncrs.append(0)

# 全部選んで選びすぎを引く
# dup を 1 つ選び、その他を dup より端から選ぶ組み合わせが重複する
ans_ncrs = get_ncrs(N + 1)
while len(ans_ncrs) < N + 2:
    ans_ncrs.append(0)
ans = [(ans_ncrs[k] - side_ncrs[k - 1]) % MOD for k in range(1, N + 2)]

print('\n'.join(map(str, ans)))