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):


SIZE=300000; MOD=10**9+7 

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

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


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i)-1 for i in readline().split()]

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



"""
for k in range(1,n+2):
    res = 0
    for l in range(k):
        res += choose(p,l)*choose(q,k-1-l)
    
    print((choose(n+1,k) - res)%MOD)
"""

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

Solution (Python):
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)

Solution (Python):
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

L = [-1] * (n + 1)
for i in range(n + 1):
  if L[a[i]] == -1:
    L[a[i]] = i
  else:
    l = L[a[i]]
    r = i

s = n - r + l
com = comb(n + 1, MOD)
for i in range(1, n + 2):
  
  if i < n:
    ans = com.com(n - 1, i)
  else:
    ans = 0
  
  if 1 <= i <= n:
    ans+= com.com(n - 1, i - 1) * 2
    if i - 1 <= s:
      ans -= com.com(s, i - 1)
    ans %= MOD
  
  if 1 < i:
    ans = (ans + com.com(n - 1, i - 2)) % MOD
  print(ans)

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
mod=10**9+7
c=[-1]*(n+1)
for i,j in enumerate(l,1):
    if(c[j]==-1):
        c[j]=i
    else:
        i1,i2=c[j],i
        break
fra=[1]*(n+2)
inv=[1]*(n+2)
c=1
t=1
for i in range(1,n+2):
    c*=i
    c%=mod
    t*=pow(i,mod-2,mod)
    t%=mod
    fra[i]=c
    inv[i]=t
def comb(n,r):
    return fra[n]*inv[n-r]*inv[r]%mod
for i in range(1,n+2):
    t=n-i2+i1
    if t+1<i:
        print(comb(n+1,i))
    else:
        print((comb(n+1,i)-comb(t,i-1))%mod)

Solution (Python):
mod = 10**9+7
fact = [1]*(10**5+2)
for n in range(1,10**5+2):
    fact[n] = n*fact[n-1]%mod
def comb(n,k):
    return fact[n]*pow(fact[k],mod-2,mod)*pow(fact[n-k],mod-2,mod)%mod

N = int(input())
a = list(map(int,input().split()))
c = [-1]*N
for j in range(N+1):
    if c[a[j]-1] != -1:
        break
    c[a[j]-1] = j
i = c[a[j]-1]
j = N-j

for k in range(1,N+2):
    ans = comb(N+1,k)
    if k-1<=i+j:
        ans -= comb(i+j,k-1)
    print(ans%mod)

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]
mod = 10**9 + 7

f = [1] * (N + 2)
fi = [1] * (N + 2)
for i in range(2, N + 2):
    f[i] = i * f[i - 1]
    f[i] %= mod
for i in range(2, N + 2):
    fi[i] = fi[i - 1] * pow(i, mod - 2, mod)
    fi[i] %= mod


def comb(n, r):
    if 0 <= n and 0 <= r and 0 <= n - r:
        return (f[n] * fi[r] * fi[n - r]) % mod
    else:
        return 0


b = set()
for a in A:
    if a in b:
        break
    b.add(a)
c = []
for i in range(N + 1):
    if A[i] == a:
        c += [i]
i, j = c
for x in range(1, N + 2):
    print((comb(N + 1, x) - (comb(N - j + i, x - 1))) % mod)

Solution (Python):
from collections import Counter, deque, defaultdict
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7
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
 
size = 2*10**5 + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] 
g2[:2] = [1, 1] 
inverse[:2] = [0, 1] 
 
for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD


N = int(input())
A = inpl()
C = Counter(A)
for k, v in C.items():
    if v == 2:
        break
l = A.index(k)
r = N - A[::-1].index(k)

d = r - l - 1

print(N)
print((1 + N-1 + d + cmb(N-1, 2, MOD))%MOD)
for k in range(3, N+2):
    X = cmb(N-1, k-1, MOD)
    Y = cmb(N-1-d, k-1, MOD)
    Z = X - Y
    tmp = cmb(N-1, k, MOD) + Y + 2*Z + cmb(N-1, k-2, MOD)
    print(tmp%MOD)

Solution (Python):
import collections

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

c = collections.Counter(a)
dup = c.most_common()[0][0]

id = [i for i, x in enumerate(a) if x == dup]
L = id[0]
R = id[1]

MOD = 10**9 +7
factorial = [1]
inverse = [1]

for i in range(1, N+2):
    factorial.append(factorial[i-1] * i % MOD)
    inverse.append(pow(factorial[i], MOD-2, MOD))
    

def C(n, r):
    if n < r:
        return 0
    return (factorial[n] * inverse[r] * inverse[n-r]) % MOD

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

Solution (Python):



MOD = 10**9+7
U = 10**5 + 1

def power_mod(a,n):
  if n == 0:
    return 1
  x = (power_mod(a,n//2)**2)%MOD
  return x if n%2 == 0 else (a*x)%MOD

def make_fact(fact,fact_inv):
  for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
  fact_inv[U] = power_mod(fact[U],MOD-2)
  for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n,k):
  if k < 0 or k > n:
    return 0
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x

fact = [1]*(U+1)
fact_inv = [1]*(U+1)
make_fact(fact,fact_inv)


n = int(input())
A = [int(x) for x in input().split()]

memo = dict()
d = 0
for i,x in enumerate(A):
  if x in memo:
    d = i - memo[x]
    break
  memo[x] = i

rest = n-d

for k in range(1,n+2):
  ans = comb(n+1,k) - comb(rest,k-1)
  ans %= MOD
  print(ans)

Solution (Python):





from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)


def main():
    n,*a=map(int,open(0).read().split())
    mod=10**9+7
    b=Counter(a).most_common()[0][0]
    l=a.index(b)
    r=a.index(b,l+1)
    n+=1
    nd=l+n-r-1
    
    inv=[0]*(n+1)
    inv[1]=1
    for i in range(2,n+1):
        inv[i]=(-(mod//i)*inv[mod%i])%mod
    tmp=n
    tmp2=1
    print(n-1)
    for i in range(2,n+1):
        tmp=(tmp*(n-i+1)*inv[i])%mod
        tmp2=(tmp2*(nd-i+2)*inv[i-1])%mod
        print((tmp-tmp2)%mod)


if __name__ == '__main__':
    main()

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    class BigCombination(object):
        __slots__=["mod", "factorial", "inverse"]

        def __init__(self, mod: int=10**9+7, max_n: int=10**6):
            fac, inv=[1], []
            fac_append, inv_append=fac.append, inv.append

            for i in range(1, max_n+1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod-2, mod))

            for i in range(max_n, 0, -1):
                inv_append(inv[-1] * i % mod)

            self.mod, self.factorial, self.inverse=mod, fac, inv[::-1]

        def get_combination(self, n, r):
            if n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod
    N = I()
    A = LI()
    d = dict()
    BC = BigCombination()
    comb = BC.get_combination
    for i, a in enumerate(A):
        if a in d:
            dabu=(i, d[a])
            break
        else:
            d[a] = i
    out = min(dabu) + N - max(dabu)
    for k in range(1, N + 2):
        ans = comb(N + 1, k) - comb(out, k - 1)
        print(ans%mod)
if __name__ == '__main__':
    main()

Solution (Python):
def factorials(M):
    INF=int(1e9+7)
    fac=[0]*(M+1)
    finv=[0]*(M+1)
    inv=[0]*(M+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,M+1):
        fac[i]=(fac[i-1]*i)%INF
        inv[i]=INF-(inv[INF%i]*(INF//i))%INF
        finv[i]=finv[i-1]*inv[i]%INF
    return fac,finv
def nCr(n,r):
    INF=int(1e9+7)
    if n<r or r<0 or n<0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%INF)%INF

N=int(input())
fac,finv=factorials(N+1)
A=list(map(int,input().split()))
INF=int(1e9+7)
d=[0]*(N+1)
for i in A:
    d[i]+=1
key=-1
for i in range(1,N+1):
    if d[i]==2:
        key=i
a,b,c=0,0,0
t=0
for i in range(N+1):
    if key==A[i]:
        t+=1
    elif t==0:
        a+=1
    elif t==1:
        b+=1
    elif t==2:
        c+=1
for i in range(1,N+2):
    if i==1:
        print(N)
        continue

    print((nCr(N+1,i)-nCr(a+c,i-1))%INF)

Solution (Python):
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]


side_ncrs = get_ncrs(L + N - r)
while len(side_ncrs) < N + 2:
    side_ncrs.append(0)



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)))

Solution (Python):
class BigCombination(object):
    __slots__ = ["mod", "factorial", "inverse"]

    def __init__(self, mod: int = 10**9+7, max_n: int = 10**6):
        fac, inv = [1], []
        fac_append, inv_append = fac.append, inv.append

        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

    def get_combination(self, n, r):
        if n < r or n == 0 or r == 0:
            return 0
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

    def get_permutation(self, n, r):
        return self.factorial[n] * self.inverse[n-r] % self.mod

N = int(input())
A = [int(x) for x in input().split()]
se = []
c = sum(A) - N * (N + 1) / 2
for i in range(len(A)):
    if A[i] == c:
        se.append(i)
l = se[0]
r = se[1]
import math
mod = 10**9+7
print(N)
Big = BigCombination()

for i in range(2,N+2):
    k = Big.get_combination(N+1, i)
    
    t = Big.get_combination(l+N-r,i-1)
    res  = k -t
    print(res%mod)

Solution (Python):
mod = 10**9+7
N = int(input())
A = [int(x) for x in input().split()]
se = []
c = sum(A) - N * (N + 1) / 2
for i in range(len(A)):
    if A[i] == c:
        se.append(i)
l = se[0]
r = se[1]
import math

print(N)

factorial = [1]
inverse = [1]
for i in range(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append((pow(factorial[-1], mod - 2, mod)))


def nCr(n, r):
    if n < r or n == 0 or r == 0:
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % mod



for i in range(2,N+2):
    k = nCr(N+1, i)
    
    t = nCr(l+N-r,i-1)
    res  = k -t
    print(res % mod)

Solution (Python):
N = int(input())
li =  [ int(it) -1 for it in input().split() ] 

import sys
sys.setrecursionlimit(10000000)

from functools import lru_cache
MOD = 1000000007
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
@lru_cache(maxsize=None)
def modinv(a):
    (inv, q, gcd_val) = egcd(a, MOD)
    return inv % MOD

fac_li = [0]*( 1000009 )
if True:
  s = 1
  for i in range(1,1000001):
    s = (s*i)%MOD
    fac_li[i] = s
def factorial(k):
  if (k<=1):
    return 1
  return fac_li[k]
@lru_cache(maxsize=None)
def combination(n,m):
  return (factorial(n)*modinv(factorial(m))*modinv(factorial(n-m)))%MOD




import collections as col
c = col.Counter( li ).items()
a = [ it for it in c if it[1] == 2][0][0]
p1 = li.index(a)
p2 = li[p1+1:].index(a) + 1 + p1

H = p1 + (N-p2)


li=[]
for i in range(1,N+2):
  a =  (combination(N+1,i) - (combination(H,i-1)if (i-1)<=H else 0))%MOD
  li.append(a)
print ( "\n".join( map(str,li) ) )

Solution (Python):
n=int(input())
*A,=map(int,input().split())

cnt = [0]*n
for i,a in enumerate(A):
    a -= 1
    if cnt[a] == 0:
        cnt[a] = i+1
    else:
        N = i-cnt[a] 

p = 10**9+7
fac = [1]*n
inv = [1]*n
finv = [1]*n
for i in range(2,n):
    fac[i] = (fac[i-1]*i) %p
    inv[i] = (-inv[p%i]*(p//i)) %p
    finv[i] = (finv[i-1]*inv[i]) %p
def comb(n,k):
    if n<k : return 0
    if n<0 or k<0 : return 0
    return fac[n]*(finv[k]*finv[n-k]%p)%p

for k in range(1,n+1):
    print((comb(n-1,k)+comb(n-1,k-2)+(comb(n-1,k-1)*2-comb(n-1-N,k-1)))%p)
print(1)

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

mod = 10**9+7

class combinationmod():
  def __init__(self,MAX, mod):
    self.mod =mod
    self.fac=[0]*(MAX+1)
    self.finv=[0]*(MAX+1)
    self.inv=[0]*(MAX+1)
    self.fac[0]=self.fac[1]=1
    self.finv[0]=self.finv[1]=1
    self.inv[1]=1
    for i in range(2,MAX+1):
      self.fac[i] = self.fac[i-1]*i%self.mod
      self.inv[i] = (-self.inv[mod%i]*(mod//i))%self.mod
      self.finv[i] = self.finv[i-1]* self.inv[i] %self.mod

  def nCk(self,n,k):
    if n<k or n<0 or k<0:
      return 0
    return self.fac[n]*(self.finv[k]*self.finv[n-k]%self.mod)%self.mod
  
memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
c = combinationmod(n+1,mod)
for k in range(1,n+2):
  print((c.nCk(n+1,k) - c.nCk(L+R,k-1))%mod)

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

mod = int(1e9+7)
def invmod(a, mod):
    if a==1:
        return 1
    return -invmod(mod%a, mod) * (mod//a) %mod


memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    

_LR = [0]*(n+3)
_LCR = [0] * (n+3) 
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) 
LR[0] = 1



LCR = [0] * (n+2) 



for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * invmod(k,mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod


  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]


  
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)

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

mod = int(1e9+7)
def powermod(a, n, mod):
    r = 1
    while n>=1:
        if n%2:
            r = (r*a)%mod
        a = (a*a)%mod
        n = n//2
    return r
  
memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    

_LR = [0]*(n+3)
_LCR = [0] * (n+3) 
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) 
LR[0] = 1



LCR = [0] * (n+2) 



for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * powermod(k, mod-2, mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod


  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]


  
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)

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

mod = int(1e9+7)
def powermod(p,n,mod):
    
    if n==1:
        return p%mod
    if n%2:
        return powermod(p,n//2,mod)**2 * p %mod
    else:
        return powermod(p,n//2,mod)**2 %mod


memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    

_LR = [0]*(n+3)
_LCR = [0] * (n+3) 
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) 
LR[0] = 1



LCR = [0] * (n+2) 



for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * powermod(k, mod-2, mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod


  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]


  
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math

mod = 10**9+7



n = int(input())
a = [int(i) for i in input().split()]



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

def combinations_count(n,r):
    if n-r < 0:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod

A = copy.deepcopy(a)
A.sort()
for i in range(n+1):
    if A[i] == A[i+1]:
        double = A[i]
        break

cnt = 0
for i in range(n+1):
    if a[i] == double:
        if cnt == 0:
            l = i+1
            cnt += 1
        else:
            r = i+1

for k in range(1,n+2):
    
    ans = (combinations_count(n+1,k)-combinations_count((l+n-r),(k-1)))%mod
    print(ans)

Solution (Python):



MOD = 10**9+7
U = 10**5 + 1

def power_mod(a,n):
  if n == 0:
    return 1
  x = (power_mod(a,n//2)**2)%MOD
  return x if n%2 == 0 else (a*x)%MOD

def make_fact(fact,fact_inv):
  for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
  fact_inv[U] = power_mod(fact[U],MOD-2)
  for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n,k):
  if k < 0 or k > n:
    return 0
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x

fact = [1]*(U+1)
fact_inv = [1]*(U+1)
make_fact(fact,fact_inv)


n = int(input())
A = [int(x) for x in input().split()]

memo = dict()
d = 0
for i,x in enumerate(A):
  if x in memo:
    d = i - memo[x]
    break
  memo[x] = i

rest = n-d

for k in range(1,n+2):
  ans = comb(n+1,k) - comb(rest,k-1)
  ans %= MOD
  print(ans)

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
mod = 10 **9 + 7



factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))



def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


X = Counter(A).most_common(1)[0][0]
X_index = []
for i, a in enumerate(A, start=1):
    if a == X:
        X_index.append(i)
L, R = X_index[0], X_index[1]

for k in range(1, N + 2):
    if k == 1:
        print(N)
    else:
        print((nCr(N + 1, k) - nCr(N - R + L, k - 1)) % mod)

Solution (Python):
n = int(input()) + 1
a = [int(item) for item in input().split()]
MOD = 10**9 + 7

def mod_pow(x, n):
    ans = 1
    while(n != 0):
        if n & 1:
            ans = ans * x % MOD
        x = x * x % MOD
        n = n >> 1
    return ans

fac = [1] + [0] * n
inv_fac = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    inv_fac[i] = inv_fac[i-1] * mod_pow(i, MOD-2) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = inv_fac[n-r] * inv_fac[r] % MOD
    return tmp * fac[n] % MOD 

index = [-1] * (n+1)
l, r = 0, 0
for i, c in enumerate(a):
    if index[c] == -1:
        index[c] = i
    else:
        l = index[c]
        r = i

for i in range(1, n+1):
    total = mod_nCr(n, i)
    doubled = mod_nCr(n -(r-l) - 1, i-1)
    ans = total - doubled
    if ans < 0:
        ans += MOD
    print(ans)

Solution (Python):
import sys

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

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    factrial = [1] * (N+2)
    for k in range(1, N+2):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (N+2)
    fact_inv[N+1] = pow(factrial[N+1], MOD - 2, MOD)
    for k in range(N, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    def comb(n, r, MOD):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD

    m = first + (N - second)
    for i in range(1, N+2):
        ans = comb(N+1, i, MOD) - comb(m, i-1, MOD)
        print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
d = {}
L, R = -1, -1
for i in range(n + 1):
    if a[i] in d:
        L = d[a[i]] + 1
        R = i + 1
        break
    else:
        d[a[i]] = i

MOD = 10 ** 9 + 7
M = 100005
fact = [0] * M
fact[0] = 1
for i in range(1, M):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

rfact = [0] * M
rfact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(M - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1)
    rfact[i] %= MOD

def comb(x, y):
    if x < 0 or y < 0 or x < y:
        return 0
    return fact[x] * rfact[y] * rfact[x - y] % MOD


for i in range(1, n + 2):
    print((comb(n + 1, i) - comb(n + 1 - R + L - 1, i - 1)) % MOD)

Solution (Python):
def mod_inv(n: int, mod: int)->int:
    b, u, v = mod, 1, 0
    while b > 0:
        t = n // b

        n -= t * b
        u -= t * v

        n, b = b, n
        u, v = v, u

    return (u+mod) % mod


def _11(N: int, A: list)->list:
    MOD = 10**9 + 7

    d = {}
    l, r = 0, 0
    for i, a in enumerate(A):
        if a in d:
            l, r = d[a], N-i
        else:
            d[a] = i

    c1, c2 = [1]*(N+2), [1]*(N+2)
    for i in range(N+1):
        c1[i+1] = (c1[i] * (N+1-i) * mod_inv(i+1, MOD)) % MOD
        c2[i+1] = (c2[i] * (l+r-i) * mod_inv(i+1, MOD)) % MOD

    return [(c1[k+1]-c2[k]+MOD) % MOD for k in range(N+1)]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _11(N, A)
    print('\n'.join(map(str, ans)))

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
idx=dict()
mod=10**9+7
for i in range(1+n):
    if A[i] in idx:
        x=idx[A[i]]
        y=i
        break
    idx[A[i]]=i
kaijo=[1]
for i in range(1,n+2):
    kaijo.append((kaijo[-1]*i)%mod)
gyaku=[pow(kaijo[n+1],mod-2,mod)]
from collections import deque
gyaku=deque(gyaku)
for i in range(n+1,0,-1):
    gyaku.appendleft((gyaku[0]*i)%mod)
gawa=n-1-(y-x-1)
zentai=n-1
gawa_conb=[1]
for i in range(1,1+gawa):
    if i<1+gawa//2:
        gawa_conb.append((kaijo[gawa]*gyaku[i]*gyaku[gawa-i])%mod)
    else:
        gawa_conb.append(gawa_conb[gawa-i])
gawa_conb+=[0]*(zentai-gawa)
zentai_conb=[1]
for i in range(1,1+zentai):
    if i<1+zentai//2:
        zentai_conb.append((kaijo[zentai]*gyaku[i]*gyaku[zentai-i])%mod)
    else:
        zentai_conb.append((zentai_conb[zentai-i]))
if n>1:
    print((zentai_conb[1]+zentai_conb[0]*2-gawa_conb[0])%mod)
    for i in range(2,n):
        print((zentai_conb[i-2]+zentai_conb[i]+zentai_conb[i-1]*2-gawa_conb[i-1])%mod)
    print((zentai_conb[n-2]+zentai_conb[n-1]*2-gawa_conb[n-1])%mod)
    print((zentai_conb[n-1])%mod)
else:
    print(1)
    print(1)

Solution (Python):
mod = int(1e9) + 7


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, y//2)**2 % mod
    else:
        return power(x, y//2)**2 * x % mod


fact = [1] * int(1e5+2)
for i in range(1, int(1e5+2)):
    fact[i] = (i * fact[i-1]) % mod
inv = [1] * int(1e5+2)
inv[int(1e5+1)] = power(fact[int(1e5+1)], mod-2) % mod
for i in range(int(1e5), 0, -1):
    inv[i] = (inv[i+1] * (i+1)) % mod


def combination(n, r):
    return fact[n] * inv[r] * inv[n-r] % mod


def main():
    N = int(input())
    A = list(map(int, input().split()))
    idx = [-1] * (N+1)
    x = 0
    for i in range(N+1):
        if idx[A[i]] == -1:
            idx[A[i]] = i
        else:
            x = i - idx[A[i]]
    for i in range(1, N+2):
        ans = combination(N+1, i)
        if i <= (N+1-x):
            ans = (ans - combination(N+1-(x+1), i-1)) % mod
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






"""
n = I()
a = LI()
b = [None for i in range(n)]
k = n//2
if n%2:
    for i in range(n):
        if i%2:
            b[k+(i+1)//2] = a[i]
        else:
            b[k-i//2] = a[i]
else:
    for i in range(n):
        if i%2:
            b[k-(i+1)//2] = a[i]
        else:
            b[k+i//2] = a[i]
print(*b)
"""


n = I()
a = LI()
fact = [1 for i in range(n+2)]
for i in range(1,n+2):
    fact[i]*= fact[i-1]*i
    fact[i] %= mod
inv_fact = [1 for i in range(n+2)]
inv_fact[n+1] = pow(fact[n+1],mod-2,mod)
for i in range(1,n+1)[::-1]:
    inv_fact[i] = inv_fact[i+1]*(i+1)
    inv_fact[i] %= mod
count = [None for i in range(n+1)]
for i in range(n+1):
    if count[a[i]] != None:
        l = count[a[i]]
        r = n-i
        break
    count[a[i]] = i
for i in range(1,n+2):
    ans = fact[n+1]*inv_fact[i]*inv_fact[n+1-i]%mod
    if l+r >= i-1:
        ans -= fact[l+r]*inv_fact[i-1]*inv_fact[l+r-i+1]%mod
        ans %= mod
    print(ans)

Solution (Python):
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 = int(input())
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 )

li=list(map(int,input().split()))
cl=[0]*N
for i in range(N+1):
    cl[li[i]-1]+=1
hu=0
for i in range(N):
    if cl[i]==2:
        hu=i+1
h1=-1
h2=-1
for i in range(N+1):
    if h1==-1 and li[i]==hu:
        h1=i
    if h1>=0 and li[i]==hu:
        h2=N-i

print(N)
for i in range(N):
    print((cmb(N+1,i+2,mod)-cmb(h1+h2,i+1,mod))%mod)

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

class ModInv:
    def __init__(self, size, MOD):
        self.inv = [0] * (size + 1)
        self.inv[1] = 1
        for i in range(2, size + 1):
            self.inv[i] = (-(MOD // i) * self.inv[MOD%i]) % MOD

if n == 1:
    print(1)
    print(1)
    exit()

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        break

first = a.index(b[i])
for i in range(first + 1, n + 1):
    if a[i] == a[first]:
        second = i

w = n + first - second

inv = ModInv(n + 1, MOD)
c = [1] * (n + 2)
d = [1] * (n + 2)

for i in range(n + 1):
    d[i + 1] = (d[i] * inv.inv[i + 1]) % MOD
for i in range(n + 1):
    c[i + 1] = (c[i] * (i + 1)) % MOD

print(n)
for k in range(2, n + 2):
    ans = (((c[n+1] * d[n+1-k]) % MOD) * d[k]) % MOD
    if w >= k - 1:
        ans -= (((c[w] * d[w-k+1]) % MOD) * d[k-1]) % MOD
    print( ans % MOD )