Problem:
 Score : 600 points    Problem Statement You are given an integer sequence of length n+1 , a_1,a_2,...,a_{n+1} , which consists of the n integers 1,...,n .
It is known that each of the n integers 1,...,n appears at least once in this sequence.  For each integer k=1,...,n+1 , find the number of the different subsequences (not necessarily contiguous) of the given sequence with length k , modulo 10^9+7 .      Notes   If the contents of two subsequences are the same, they are not separately counted even if they originate from different positions in the original sequence.    A subsequence of a sequence a with length k is a sequence obtained by selecting k of the elements of a and arranging them without changing their relative order. For example, the sequences 1,3,5 and 1,2,3 are subsequences of 1,2,3,4,5 , while 3,1,2 and 1,10,100 are not.        Constraints  1 \leq n \leq 10^5  1 \leq a_i \leq n  Each of the integers 1,...,n appears in the sequence.  n and a_i are integers.         Input Input is given from Standard Input in the following format:  n  a_1  a_2 ... a_{n+1}       Output Print n+1 lines.
The k -th line should contain the number of the different subsequences of the given sequence with length k , modulo 10^9+7 .        Sample Input 1 3
1 2 1 3      Sample Output 1 3
5
4
1  There are three subsequences with length 1 : 1 and 2 and 3 .  There are five subsequences with length 2 : 1,1 and 1,2 and 1,3 and 2,1 and 2,3 .  There are four subsequences with length 3 : 1,1,3 and 1,2,1 and 1,2,3 and 2,1,3 .  There is one subsequence with length 4 : 1,2,1,3 .       Sample Input 2 1
1 1      Sample Output 2 1
1  There is one subsequence with length 1 : 1 .  There is one subsequence with length 2 : 1,1 .       Sample Input 3 32
29 19 7 10 26 32 27 4 11 20 2 8 16 23 5 14 6 12 17 22 18 30 28 24 15 1 25 3 13 21 19 31 9      Sample Output 3 32
525
5453
40919
237336
1107568
4272048
13884156
38567100
92561040
193536720
354817320
573166440
818809200
37158313
166803103
166803103
37158313
818809200
573166440
354817320
193536720
92561040
38567100
13884156
4272048
1107568
237336
40920
5456
528
33
1  Be sure to print the numbers modulo 10^9+7 .

Solution (Python):
class Combination:
    def __init__(self, n_max, MOD=10 ** 9 + 7):
        """
        前処理 = O(n_max + log(MOD))
        :param self.fac[n]: n!
        :param self.facinv[n]: 1/n!
        """
        self.mod = MOD
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % MOD
            fac.append(f)
        f = pow(f, MOD - 2, MOD)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % MOD
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0                    
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

MOD = 10**9 + 7
N = int(input())
C = Combination(N+1)
v = {}
for i, a in enumerate(map(int, input().split()),start=1):
    if v.get(a,0)==0:
        v[a] = i
    else:
        L = i-v[a]
        break
for l in range(1,N+2):
    print((C(N+1,l)-C(N-L,l-1))%MOD)

Solution (Python):
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
MAX = 10**5 + 100
MOD = 10**9 + 7

def COMinit():
    """
    逆元テーブルをつくる前処理
    計算量はO(n)
    1 <= k <= n <= 1e7程度
    p: 素数
    """
    fac = [0]*MAX
    finv = [0]*MAX
    inv = [0]*MAX

    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[0], inv[1] = 1, 1
    for i in range(2, MAX):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD
    return fac, finv, inv



def comb(n, k):
    """
    nCk mod MODを求める.
    O(1)
    """
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return int(fac[n] * (finv[k] * finv[n-k] % MOD) % MOD)

fac, finv, inv = COMinit()


counter = dict(Counter(A))
dual = 0 
for key, value in counter.items():
    if value == 2:
        dual = key
        break

L = A.index(dual)
R = N - A.index(dual, L+1)

for K in range(1, N+2):
    ans = comb(N+1, K) - comb(L+R, K-1)
    
    print(ans%MOD)

Solution (Python):
import collections

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
K = 2*(10**5)
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, K + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
n=int(input())
print(n)
nCk=n
R=list()
L=list(map(int,input().split()))
c = collections.Counter(L)
nikai=c.most_common()[0][0]
for i in range(n+1):
  if L[i]==nikai:
    R.append(i)

k=n-R[1]+R[0]
for i in range(1,n):
  nCk=cmb(n+1,i+1,mod)
  a = cmb(k,i,mod)
  print((nCk-a)%mod)
print(1)

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


def main():
	
	n=II()
	A=LI()
	m=10**9+7
	
	x=sum(A)-n*(n+1)//2
	
	l=A.index(x)
	r=A.index(x,l+1)
	
	lr=l+n-r
	
	C=[1]
	D=[1]
	
	for i in range(1,n+2):
		C.append((C[-1]*(n+2-i)*pow(i,m-2,m))%m)
	
	for i in range(1,n+2):
		if i>lr:
			D.append(0)
		else:
			D.append((D[-1]*(lr+1-i)*pow(i,m-2,m))%m)
	
	
	
	
	
	for i in range(1,n+2):
		print((C[i]-D[i-1])%m)
	
	
	
	

if __name__=="__main__":
	main()

Solution (Python):
def examC():
    ans = 0
    print(ans)
    return

def examD():
    class combination():
        
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    N = I()
    A = LI()
    D = {}
    l = -1; r = -1
    for i,a in enumerate(A):
        if a in D:
            l = D[a]
            r = i
            break
        D[a] = i
    
    C = combination(N+2,mod)
    ans = [0]*(N+1)
    for i in range(1,N+2):
        ans[i-1] = (C.comb(N+1,i) - C.comb(l+N-r,i-1) + mod) % mod

    for v in ans:
        print(v)
    return

def examE():
    N, M = LI()
    A = LI()
    S = [0]*(M+2)
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        S[a0+1] += 1
        S[a1] -= 1
        if a1<a0:
            S[0] += 1
    
    for i in range(M):
        S[i+1] += S[i]
    for i in range(M+1):
        if S[i]<0:
            S[i] = 0
    D = defaultdict(int)
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        cost = (a1 + M - a0) % M - 1
        D[a1] += cost
    start = 0
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        cost = min(a1, (a1+M-a0)%M)
        start += cost
    
    
    
    cost = start
    ans = start
    for i in range(1,M):
        cost += (D[i] - S[i])
        
        if ans>cost:
            ans = cost
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
SIZE=10**5+10; MOD=10**9+7 

SIZE += 1
inv = [0]*SIZE  
fac = [0]*SIZE  
finv = [0]*SIZE 
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    fac[i] = fac[i-1]*i%MOD
finv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(SIZE-1,0,-1):
    finv[i-1] = finv[i]*i%MOD
    inv[i] = finv[i]*fac[i-1]%MOD

def choose(n,r): 
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0



import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

r = [-1]*(n+1)
for i,ai in enumerate(a):
    if r[ai]==-1:
        r[ai] = i
    else:
        p = r[ai]
        q = i
        break


for i in range(1,n+2):
    ans = choose(n+1,i)
    ans -= choose(p+n-q,i-1)
    print(ans%MOD)

Solution (Python):
from collections import Counter
import numpy as np

N = 10 ** 6
Nsq = 10 ** 3
mod = 10 ** 9 + 7

fac = np.arange(N, dtype=np.int64).reshape(Nsq, Nsq)
fac[0, 0] = 1
for i in range(1, Nsq):
    fac[:, i] *= fac[:, i - 1]
    fac[:, i] %= mod
for i in range(1, Nsq):
    fac[i] *= fac[i - 1, -1]
    fac[i] %= mod
fac = fac.ravel()

finv = np.arange(1, N + 1, dtype=np.int64)[::-1].reshape(Nsq, Nsq)
finv[0, 0] = pow(int(fac[N - 1]), mod - 2, mod)
for i in range(1, Nsq):
    finv[:, i] *= finv[:, i - 1]
    finv[:, i] %= mod
for i in range(1, Nsq):
    finv[i] *= finv[i - 1, -1]
    finv[i] %= mod
finv = finv.ravel()[::-1]


def nCr(a, b):
    if b > a:
        return 0
    else:
        comb = fac[a] * finv[b] % mod * finv[a - b] % mod
        return comb


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

ind = 0
for i, x in enumerate(A):
    if C[x] > 1:
        ind = i - ind

for i in range(1, n + 2):
    res = nCr(n + 1, i) - nCr(n - ind, i - 1)
    res %= mod
    print(res)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7



max = 1 * 10**5 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max)


def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ind = [-1] * (1+n)
for i,ai in enumerate(a,1):
    if(ind[ai]==-1):
        ind[ai] = i
    else:
        left = ind[ai]
        right = i
        break

ans = [0] * (n+2)
for k in range(1,n+2):
    cnt = com(n+1,k)
    if(n -(right-left) >= k-1 ):
        cnt -= com(n-(right-left),k-1)
    ans[k] = cnt%mod

print('\n'.join(map(str,ans[1:])))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7



max = 1 * 10**5 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max)


def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ind = [-1] * (1+n)
for i,ai in enumerate(a,1):
    if(ind[ai]==-1):
        ind[ai] = i
    else:
        left = ind[ai]
        right = i
        break

ans = [0] * (n+2)
for k in range(1,n+2):
    cnt = com(n-1,k) + com(n-1,k-1)*2 - com(n - (right-left),k-1)
    if(k >= 2):
        cnt += com(n-1,k-2)
    ans[k] = cnt%mod

print('\n'.join(map(str,ans[1:])))

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import defaultdict
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    A = list(map(int, readline().split()))

    d = defaultdict(list)
    for i in range(N+1):
        d[A[i]].append(i)

    for i in range(1,N+1):
        if len(d[i]) == 2:
            left, right = d[i]
            break

    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]

    for i in range(2, N + 2):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)

    def cmb(n, r, mod):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return fact[n] * factinv[r] * factinv[n - r] % mod

    for k in range(1,N+2):
        ans = cmb(N+1,k,MOD) - cmb(left-1+N-right+1,k-1,MOD)
        print(ans%MOD)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

n = I()
a = LI()
mod = 10**9+7

from collections import defaultdict

d = defaultdict(list)

for i in range(n+1):
    d[a[i]].append(i)

for i in range(1,n+1):
    if len(d[i]) == 2:
        b,c = d[i]  

kaijou = [1]  
for i in range(1,n+2):
    kaijou.append((kaijou[-1]*i) % mod)

def comb(m,i):  
    if m < i:
        return 0
    else:
        return (kaijou[m]*pow(kaijou[i],mod-2,mod)*pow(kaijou[m-i],mod-2,mod)) % mod

for i in range(1,n+2):
    print((comb(n+1,i)-comb(n-c+b,i-1)) % mod)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
mod = 10**9+7
n = int(input())
a = list(map(int,input().split()))

def make_array_for_comb(N, mod=10**9+7):
    fact = [1,1]
    fact_inv = [1,1]
    inv = [0,1]
    for i in range(2, N+1):
        fact.append((fact[-1]*i) % mod)
        
        inv.append((-inv[mod%i] * (mod//i)) % mod)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

fact, fact_inv = make_array_for_comb(n+1,mod)
c = Counter(a)
k = c.most_common()[0][0]
t = 0
for i,ai in enumerate(a):
  if ai == k:
    if t == 0:
      L = i
    elif t == 1:
      R = n-i
      break
    t += 1
    
print(n)
for i in range(1,n+1):
  print((comb(n+1,i+1,mod)-comb(L+R,i,mod))%mod)

Solution (Python):
N = int(input())
A = tuple(map(int, input().split()))

MOD = 10 ** 9 + 7
MAX = 10 ** 5 + 10
modinv = lambda a, mod=MOD: pow(a, mod - 2, mod)
fac, inv = [1] * MAX, [1] * MAX
for i in range(1, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = modinv(fac[i])


def comb(n, k, error=0):
    if not 0 <= k <= n:
        return error
    return fac[n] * inv[k] * inv[n - k] % MOD


d_tmp = {}
for i, a in enumerate(A):
    if a in d_tmp:
        double = a
        lr_sections_len = d_tmp[a] + N - i
        break
    else:
        d_tmp[a] = i

for k in range(1, N + 2):
    print((comb(N + 1, k) - comb(lr_sections_len, k - 1)) % MOD)

Solution (Python):


def LI():
    return list(map(int, input().split()))


N = int(input())
A = LI()

MOD = 10 ** 9 + 7
MAX = 10 ** 5 + 5
fac, finv, inv = [None] * MAX, [None] * MAX, [None] * MAX


def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = -inv[MOD%i] * int(MOD / i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


def main():
    comb_init()
    d = {i: [] for i in range(1, N + 1)}
    x, y = [None] * 2
    for i in range(N + 1):
        d[A[i]].append(i)
        if len(d[A[i]]) == 2:
            x, y = d[A[i]]
            break
    
    for i in range(1, N + 2):
        ans = comb(N + 1, i)
        ans -= comb(N + x - y, i - 1)
        ans %= MOD
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int,input().split()))

c = Counter(a)
twice_num = c.most_common(1)[0][0]

left_cnt = 0
right_cnt = 0
state = 0
for i in a:
    if i == twice_num and state == 0:
        state = 1
        continue
    if i == twice_num and state == 1:
        state = 2
        continue

    if state == 0:
        left_cnt += 1
    if state == 2:
        right_cnt += 1



def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9 + 7
N = n+2 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


for i in range(1,n+2):
    print((cmb(n+1,i,mod) - cmb(left_cnt + right_cnt,i-1,mod))%mod)

Solution (Python):
from collections import Counter

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

MOD = 10 ** 9 + 7



n = nn + 3
fac = [1] * (n + 1) 
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = (fac[j - 1] * j) % MOD

inv[n] = pow(fac[n], MOD-2, MOD)
for j in range(n - 1, -1, -1):
    inv[j] = (inv[j + 1] * (j + 1)) % MOD

def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return (fac[n] * inv[n - r] * inv[r]) % MOD

duple = Counter(A).most_common()[0][0]

l = A.index(duple)
r = A.index(duple, l+1)

outer = nn - (r - l)

for i in range(1, nn + 2):
  print((comb(nn + 1, i) - comb(outer, i - 1)) % MOD)

Solution (Python):
n=int(input())
A=list(map(int, input().split()))
B=sorted(A)
for i in range(n+1):
  if B[i]!=i+1:
    a=i
    break
d=[i for i, x in enumerate(A) if x==a]
x=d[0]
y=d[1]

def cmb(n,r,mod):
    if (r<0 or r>n):
      return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod

mod=10**9+7 
N=10**5+10
g1=[1,1] 
g2=[1,1] 
inverse=[0,1] 

for i in range(2,N+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

for i in range(1,n+2):
  ans=cmb(n+1,i,mod)-cmb(x+(n-y),i-1,mod)
  print(ans%mod)

Solution (Python):
n=int(input())
A=list(map(int, input().split()))
B=sorted(A)
for i in range(n+1):
  if B[i]!=i+1:
    a=i
    break
d=[i for i, x in enumerate(A) if x==a]
x=d[0]
y=d[1]

def cmb(n,r,mod):
    if (r<0 or r>n):
      return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod

mod=10**9+7 
N=10**5+10
g1=[1,1] 
g2=[1,1] 
inverse=[0,1] 

for i in range(2,N+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

for i in range(1,n+2):
  ans=cmb(n+1,i,mod)-cmb(x+(n-y),i-1,mod)
  if ans<0:
    print(mod+ans)
  else:
    print(ans)

Solution (Python):
nmax = 10**6
mod = 10**9+7

fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) %mod
        finv[i] = finv[i-1] * inv[i] %mod

def ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod

ncr_pre()
n = int(input())
A = list(map(int,input().split()))
co = [0]*(n+2)
id2 = -1
for i in  range(n+1):
    a = A[i]
    co[a]+=1
    if co[a]==2:
        id2 = i
        break
id1 = A.index(a)
d = n-id2 +id1

for k in range(1,n+2):
    ans = ncr(n+1,k)
    if k-1<=d:
        ans -= ncr(d,k-1)
    print(ans%mod)

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

MOD = 10**9+7
 
MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
 
def nCr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD




idxs = [[] for _ in range(N)]
for i,a in enumerate(A):
    idxs[a-1].append(i)

for i in range(N):
    if len(idxs[i]) == 2:
        first = idxs[i][0]
        second = idxs[i][1]
        break

for i in range(1, N+2):
    if i == 1:
        print(N)
    elif i == N+1:
        print(1)

    else:
        a = nCr(N+1, i)
        
        cnt = first + (N-second)
        if cnt >= i-1:
            a -= nCr(cnt, i-1)
            a %= MOD
        
        print(a)

Solution (Python):
import copy
def comb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
b=copy.deepcopy(a)
b.sort()
x=0
s=[]
for i in range(1,n+1):
  if b[i-1]==b[i]:
    x=b[i]
for i in range(n+1):
  if a[i]==x:
    s.append(i)
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
for i in range( 2, n + 2 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
for k in range(1,n+2):
  print((comb(n+1,k,mod)-comb(n-s[1]+s[0],k-1,mod))%mod)

Solution (Python):

n = int(input())
n += 1
a = list(map(int,input().split()))
b = []
for i in range(n):
  b.append([a[i],i])
b.sort()
for j in range(n-1):
  if b[j][0] == b[j+1][0]:
    k = b[j+1][1] - b[j][1] - 1
mod = 10 ** 9 + 7
now = [ n-k-2 , 1 , 0 , n , n-k ]

print(sum(now)-2*now[-1])
now = [ (n-k-2)*(n-k-3)//2 , n-k-2 , 1 , n*(n-1)//2 , (n-k)*(n-k-1)//2 ]

print((sum(now)-2*now[-1]) % mod)

def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y

for i in range(3,n+1):
  last = now
  now = [0 for _ in range(5)]
  now[0] = last[0] * (n-k-i-1) * inv(i)
  now[1] = last[1] * (n-k-i)   * inv(i-1)
  now[2] = last[2] * (n-k-i+1) * inv(i-2)
  now[3] = last[3] * (n  -i+1) * inv(i)
  now[4] = last[4] * (n-k-i+1) * inv(i)
  for d in range(5):
    now[d] %= mod
  
  print((sum(now)-2*now[-1]) % mod)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
L=[0 for i in range(n+1)]
for i in range(n+1):
    L[a[i]]+=1

D=0
for i in range(1,n+1):
    if L[i]==2:
        D=i

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**5+10
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

P=[0,0,0]
One=0

for i in range(n+1):
    if a[i]==D:
        One+=1
    else:
        P[One]+=1

for i in range(1,n+2):
    print((cmb(n+1,i,mod)-cmb(P[0]+P[2],i-1,mod))%mod)

Solution (Python):
mod = 10 ** 9 + 7

f = [0 for _ in range(200000)]
f[0] = 1
for i in range(1, 200000):
    f[i] = f[i - 1] * i % mod
inv = [pow(f[i], mod - 2, mod) for i in range(200000)]


def C(n, m):
    if n < m or m < 0: return 0
    return f[n] * inv[m] * inv[n - m] % mod

n = int(input())
a = list(map(lambda x: int(x) - 1, input().split()))
pos = [[] for _ in range(n)]

for idx, x in enumerate(a):
    pos[x].append(idx)

for _ in pos:
    if len(_) == 2:
        l, r = _

for i in range(1, n + 2):
    print(((C(n + 1, i) - C(n + l - r, i - 1)) % mod + mod) % mod)

Solution (Python):
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (2*10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, = map(int, input().split())
ps = list(map(int, input().split()))
p2i = dict()
i = 0
for p in ps:
    if p not in p2i:
        i += 1
        p2i[p] = i
        continue
    x = p2i[p]
    break
X = min(x-1, i-1)
Y = min(N-x, N-i)
for i in range(1, N+2):
    print((cmb(N+1, i) - cmb(X+Y, i-1))%mod)

Solution (Python):

from collections import Counter
MAX = 310000
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX



def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD



def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD



COMinit()

N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
count = sorted(count.items(), key=lambda x: x[1], reverse=True)

dual = count[0][0]
t = 0
for i in range(len(A)):
    if A[i] == dual:
        if t == 0:
            l = i
        else:
            r = i
        t += 1
for k in range(1, N+2):
    print((COM(N+1, k) - COM(l+N-r, k-1) + MOD) % MOD)

Solution (Python):

MAX = 310000
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX



def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD



def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD



COMinit()
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
count = sorted(count.items(), key=lambda x: x[1], reverse=True)

dual = count[0][0]
t = 0
for i in range(len(A)):
    if A[i] == dual:
        if t == 0:
            l = i
        else:
            r = i
        t += 1
for k in range(1, N+2):
    print((COM(N+1, k) - COM(l+N-r, k-1) + MOD) % MOD)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import Counter

import numpy as np

MOD = 10 ** 9 + 7

N = int(readline())
A = np.array(read().split(),np.int32)

counter = np.bincount(A)
x = np.argmax(counter)
I,J = np.where(A == x)[0]

L = I
M = J - I - 1
R = N - J



def cumprod(A, MOD = MOD):
    L = len(A); Lsq = int(L**.5+1)
    A = np.resize(A, Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        A[:,n] *= A[:,n-1]; A[:,n] %= MOD
    for n in range(1,Lsq):
        A[n] *= A[n-1,-1]; A[n] %= MOD
    return A.ravel()[:L]
def make_fact(U, MOD = MOD):
    x = np.arange(U, dtype = np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact,fact_inv

fact, fact_inv = make_fact(10 ** 5 + 100)

answer = fact[N+1] * fact_inv[:N+2] % MOD * fact_inv[:N+2][::-1] % MOD
LR = L + R
x = fact[LR] * fact_inv[:LR+1] % MOD * fact_inv[:LR+1][::-1] % MOD
answer[1:LR+2] -= x

answer = answer[1:]
answer %= MOD
print('\n'.join(answer.astype(str)))

Solution (Python):
N = int(input())
X = [-1] * N
A = [int(a)-1 for a in input().split()]
a, b, c = 0, 0, 0
for i in range(N+1):
    if X[A[i]] >= 0:
        a = X[A[i]]
        b = i - X[A[i]] - 1
        c = N - i
        break
    else:
        X[A[i]] = i

P = 10**9+7
fa = [1]
for i in range(1, N + 10):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, N + 10)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]

def C(i, j):
    if j < 0 or j > i: return 0
    return fa[i] * fainv[j] % P * fainv[i-j] % P

for K in range(1, N+2):
    ans = C(N-1, K)
    ans += C(a+c, K-1) + 2 * (C(a+b+c, K-1) - C(a+c, K-1))
    ans += C(a+b+c, K-2)
    ans %= P
    print(ans)

Solution (Python):
N = int(input())
X = [-1] * N
A = [int(a)-1 for a in input().split()]
a, b, c = 0, 0, 0
for i in range(N+1):
    if X[A[i]] >= 0:
        a = X[A[i]]
        b = i - X[A[i]] - 1
        c = N - i
        break
    else:
        X[A[i]] = i

P = 10**9+7
fa = [1]
for i in range(1, N + 10):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, N + 10)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]

def C(i, j):
    if j < 0 or j > i: return 0
    return fa[i] * fainv[j] % P * fainv[i-j] % P

for K in range(1, N+2):
    ans = C(N-1, K)
    ans += C(a+c, K-1) + 2 * (C(a+b+c, K-1) - C(a+c, K-1))
    ans += C(a+b+c, K-2)
    ans %= P
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from collections import deque

class SegTree():
    def __init__(self, n):
        self.value = [0 for i in range(n*2)]

MOD = 10 ** 9 + 7

def getinvmod(n):
    return [pow(i, MOD-2, MOD) for i in range(n+1)]


def main():
    n = getN()
    nums = getList()
    index = [-1 for i in range(n)]

    for i, num in enumerate(nums):
        if index[num - 1] == -1:
            index[num - 1] = i
        else:
            ida = i
            idb = index[num - 1]
            break

    side = n - (ida - idb)

    invmod = getinvmod(n+1)

    
    
    
    ans = n + 1
    minus = 1
    print((ans - minus)%MOD)
    
    for i in range(1, n + 1):
        ans *= (n - i + 1)
        ans *= invmod[i + 1]
        ans %= MOD
        if i <= side:
            minus *= side - i + 1
            minus *= invmod[i]
            minus %= MOD

        else:
            minus = 0

        print((ans - minus) % MOD)
        



if __name__ == "__main__":
    main()

Solution (Python):
mod = 10**9+7
n = int(input())
num = [ int(v) for v in input().split() ]

dup = [ None for i in range(n) ]
for i, v in enumerate(num):
    if dup[v-1] == None:
        dup[v-1] = i
    else:
        l, r = dup[v-1], n-i
        break

def all_combination_with_mod(m):
    ret_list = [ 1 for i in range(m+1) ]
    for i in range(m):
        a = ret_list[i] * (m-i) * pow(i+1,mod-2,mod)
        ret_list[i+1] = a % mod
    return ret_list

ans_list = all_combination_with_mod(n+1)[1:]
sub_list = all_combination_with_mod(l+r)


for i in range(l+r+1):
    ans_list[i] -= sub_list[i]
    ans_list[i] %= mod

for i in ans_list:
    print(i)

Solution (Python):
n = int(input())
mod = 10**9+7
fun = [1]*(n+1)
for i in range(1,n+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n+1)
rev[n] = pow(fun[n],mod-2,mod)
for i in range(n-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

l = list(map(int,input().split()))
db = sum(l) - n*(n+1)//2
idx = [i for i in range(n+1) if l[i] == db]
a,b,c = idx[0],idx[1]-idx[0]-1,n-idx[1]
print(n)
for k in range(2,n+2):
  print((nCr(a+b+c,k)+nCr(a+b+c,k-2)+nCr(a+b+c,k-1)*2-nCr(a+c,k-1))%mod)