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):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
p = 10**9+7

n = int(input())
a = list( map(int, input().split()))
count = [0]*n

for i in range(n+1):
    count[a[i]-1] += 1
    if count[a[i]-1] == 2:
        right = i
        left = a.index(a[i])
        break

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

p = 10 ** 9 + 7
N = 10 ** 5  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

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

for i in range(1,n+2):
    ans = nCr_mod_p(n+1,i,p) - nCr_mod_p(n-right+left,i-1,p)
    print(ans%p)

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

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_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
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
def main():
    n = int(input())
    a = list(map(int, input().split()))
    p = [-1]*(n+1)
    l, r = -1, -1
    for i, v in enumerate(a):
        if p[v] == -1:
            p[v] = i
        else:
            l = p[v]
            r = i
            break
    MOD_COM_init()
    for i in range(1, n+2):
        if i == 1:
            print(n)
        else:
            tmp = MOD_COM(n+1, i)
            tmp -= MOD_COM(l+(n+1-r-1), i-1)
            while tmp < 0:
                tmp += MOD
            print(tmp)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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


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

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 )

ma=0
dic={}
for i in range(m):
    if not a[i] in dic:
        dic[a[i]]=i
    else:
        ma=i-dic[a[i]]-1

for k in range(1,m+1):
    if k==1:
        print(n)
        continue
    tmp=cmb(m,k)

    tmp-=cmb(m-2-ma,k-1)
    print(tmp%mod)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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


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

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 )

ma=0
dic={}
for i in range(m):
    if not a[i] in dic:
        dic[a[i]]=i
    else:
        ma=i-dic[a[i]]-1

for k in range(1,m+1):
    if k==1:
        print(n)
        continue
    tmp=cmb(m,k)
    if m-2-ma>=k-1:
        tmp-=cmb(m-2-ma,k-1)
    print(tmp%mod)

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

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ct=[0]*n
X=[]
for i in range(n+1):
  ct[a[i]-1]+=1
for i in range(n):
  if ct[i]==2:
    x=i+1
    break
for i in range(n+1):
  if a[i]==x:
    X.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 i in range(1,n+2):
    print((cmb(n+1,i,mod)-cmb(X[0]+n-X[1],i-1,mod)+mod)%mod)

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


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


N = int(input())
place = [0] * N
A = list(map(int, input().split()))
for i, s in enumerate(A):
    if place[s - 1] == 0:
        place[s - 1] = i + 1
    else:
        a = place[s - 1]
        b = i + 1
        break

modFacts, invs = prepare(N + 1)
cnt = pow(2, N + 1, MOD) - 1
cnt -= pow(2, a - 1, MOD) * pow(2, N + 1 - b, MOD)

la = a - 1
rb = N + 1 - b
t = la + rb
for k in range(1, N + 2):
    cnt = (modFacts[N + 1] * invs[k] * invs[N + 1 - k]) % MOD
    if t >= k - 1:
        cnt -= (modFacts[t] * invs[k - 1] * invs[t - (k - 1)])
    print(cnt % MOD)

Solution (Python):
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
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
n=int(input())
mod=10**9+7
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 )
import copy
a=list(map(int,input().split()))
b=copy.deepcopy(a)
b.sort()
tmp=-1
for i in range(n):
  if b[i]==b[i+1]:
    tmp=b[i]
r=[]
for i in range(n+1):
  if a[i]==tmp:
    r.append(i)
y=abs(r[1]-r[0]-1)
for k in range(1,n+2):
  ans=(comb(n-1,k,mod)+comb(n-1,k-2,mod)+comb(n-1,k-1,mod)*2-comb(n-1-y,k-1,mod))%mod
  print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
fac = [1] * (10 ** 5 + 10)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD


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


n = int(input())
a = list(map(int, input().split()))
d = [-1] * n
for i, x in enumerate(a):
    if d[x - 1] != -1:
        p = d[x - 1]
        q = i
    else:
        d[x - 1] = i
print(n)
for k in range(2, n + 2):
    ans = 0
    ans += comb(n - 1, k - 2)
    ans += comb(n - 1, k - 1) * 2 - comb(p + n - q, k - 1)
    ans += comb(n - 1, k)
    print(ans % MOD)

Solution (Python):
mod = 10 ** 9 + 7
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

N = 10 ** 5 + 10
fact = [0] * (N)
fact[0] = 1
for i in range(1, N):
    fact[i] = (fact[i-1] * i) % mod

def comb(a, b):
    return moddiv(moddiv(fact[a], fact[a-b]), fact[b])

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

searched = set()
for dup, x in enumerate(a):
    if x in searched:
        break
    else:
        searched.add(x)
first = a.index(a[dup])

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

Solution (Python):
from collections import Counter
import sys
input = sys.stdin.readline

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

fact = [1] * (n+2)
fact_inv = [1] * (n+2)
for i in range(1, n+2):
    fact[i] = i * fact[i-1] % mod
    fact_inv[i] = pow(fact[i], mod-2, mod)

def combination(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[k] * fact_inv[n-k] % mod

x = Counter(a).most_common(1)[0][0]
front = a.index(x)
back = a[::-1].index(x)

for k in range(1, n+2):
    ans = (combination(n+1, k) - combination(front + back, k-1)) % mod
    print(ans)

Solution (Python):
import copy

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 = 2*10**5
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 )


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

B=copy.copy(A)
B.sort()
x=0
for i in range(0,N):
    if B[i]==B[i+1]:
        x=B[i]
        break

first=-1
second=-1
for i in range(0,N+1):
    if A[i]==x:
        if first==-1:
            first=i
        else:
            second=i

for k in range(1,N+2):
    if N-1>=k:
        if first+N-second>=k-1:
            ans=2*cmb(N-1,k-1,mod)-cmb(first+N-second,k-1,mod)+cmb(N-1,k,mod)+cmb(N-1,k-2,mod)
            print(ans%mod)
        else:
            ans=2*cmb(N-1,k-1,mod)+cmb(N-1,k,mod)+cmb(N-1,k-2,mod)
            print(ans%mod)
    elif N==k:
        if first+N-second>=k-1:
            ans=2*cmb(N-1,k-1,mod)-cmb(first+N-second,k-1,mod)+cmb(N-1,k-2,mod)
            print(ans%mod)
        else:
            ans=2*cmb(N-1,k-1,mod)+cmb(N-1,k-2,mod)
            print(ans%mod)
    else:
        if first+N-second>=k-1:
            ans=-cmb(first+N-second,k-1,mod)+cmb(N-1,k-2,mod)
            print(ans%mod)
        else:
            ans=cmb(N-1,k-2,mod)
            print(ans%mod)

Solution (Python):
class COM:
    def __init__(self, n: int, mod: int):
        self.n = n
        self.mod = mod
        self.fact = [0] * (n + 1)
        self.factinv = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        
        self.fact[0] = self.fact[1] = 1
        self.factinv[0] = self.factinv[1] = 1
        self.inv[1] = 1
        for i in range(2, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % mod
            self.inv[i] = (-self.inv[mod % i] * (mod // i)) % mod
            self.factinv[i] = (self.factinv[i - 1] * self.inv[i]) % mod
    
    def get_cmb(self, n: int, k: int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] % self.mod * self.factinv[n - k] % self.mod


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    
    pos = dict()
    l, r = -1, -1
    for i in range(n + 1):
        if a[i] in pos:
            l, r = pos[a[i]], i
            break
        pos[a[i]] = i
    
    com = COM(10 ** 5 + 1, MOD)
    print(n)
    for i in range(2, n + 1):
        ans = com.get_cmb(n + 1, i) - com.get_cmb(l + n - r, i - 1)
        print(ans % MOD)
    print(1)


if __name__ == '__main__':
    solve()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
l=[None]*(n+1)
for i in range(n+1):
    if l[a[i]]==None:
        l[a[i]]=i
    else:
        p=l[a[i]]+n-i
        break
pr=10**9+7
print(n)
MAX_NUM = 10**5 + 2
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
for i in range(2,n+1):
    t=c(n+1,i)
    if p>=i-1:
        t-=c(p,i-1)
    print(t%pr)
print(1)

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 com(n,k,m):
 return fact[n]*pow(fact[k],m-2,m)*pow(fact[n-k],m-2,m)%m

N=int(raw_input())
A=map(int,raw_input().split())
c=[-1]*N
for i in range(N+1):
 if c[A[i]-1]!=-1:
  break
 c[A[i]-1]=i
j=c[A[i]-1]
i=N-i
for k in range(1,N+2):
 res=com(N+1,k,mod)
 if k-1<=i+j:
  res-=com(i+j,k-1,mod)
 print res%mod

Solution (Python):




from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys





N=int(input())
A=list(map(int,input().split()))
if N==1:
    print(1)
    print(1)
    exit()
mod=10**9+7
fac=[1,1]
for i in range(2,N+2):
    fac.append(fac[i-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]


def comb(a,b):
    if a<b:
        return(0)
    if a==0 or b==0:
        return(1)


    return(fac[a]*ifac[a-b]*ifac[b]%mod)



data=[[] for i in range(N+1)]
for i in range(len(A)):
    data[A[i]].append(i)
a,b=[i for i in data if len(i)>=2][0]

z=a+len(A)-b-1


for n in range(1,N+2):
    
    print((comb(N+1,n)-comb(z,n-1))%mod)

Solution (Python):
import collections

mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
cnt=collections.Counter(arr)
for key in cnt.keys():
  if cnt[key]==2:
    K=key
pos1=-1
pos2=-1
for i in range(n+1):
  if arr[i]==K:
    if pos1==-1:
      pos1=i
    else:
      pos2=i
A=pos1
B=pos2-pos1-1
C=n-pos2
facts=[1]
for i in range(1,n+1):
  facts.append((facts[-1]*i)%mod)
revfacts=[1]
for i in range(1,n+1):
  revfacts.append(pow(facts[i],mod-2,mod))
ans=[]
for i in range(1,n+2):
  ways1=0
  if i<=A+B+C:
    ways1=(facts[A+B+C]*revfacts[i]*revfacts[A+B+C-i])%mod
  ways2=0
  if i>=2 and i-2<=A+B+C:
  	ways2=(facts[A+B+C]*revfacts[i-2]*revfacts[A+B+C-(i-2)])%mod
  ways3=0
  if i>=1 and i-1<=A+C:
    ways3=(facts[A+C]*revfacts[i-1]*revfacts[A+C-(i-1)])%mod
  ways4=0
  if i>=1 and i-1<=A+B+C:
    ways4=(2*facts[A+B+C]*revfacts[i-1]*revfacts[A+B+C-(i-1)]-2*ways3)%mod
  ans.append((ways1+ways2+ways3+ways4)%mod)
for val in ans:
  print(val)

Solution (Python):
import collections

mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
cnt=collections.Counter(arr)
for key in cnt.keys():
  if cnt[key]==2:
    K=key
pos1=-1
pos2=-1
for i in range(n+1):
  if arr[i]==K:
    if pos1==-1:
      pos1=i
    else:
      pos2=i
A=pos1
B=pos2-pos1-1
C=n-pos2
facts=[1]
for i in range(1,n+1):
  facts.append((facts[-1]*i)%mod)
revfacts=[1]
for i in range(1,n+1):
  revfacts.append(pow(facts[i],mod-2,mod))
ans=[]
for i in range(1,n+2):
  ways1=0
  if i<=A+B+C:
    ways1=(facts[A+B+C]*revfacts[i]*revfacts[A+B+C-i])%mod
  ways2=0
  if i>=2 and i-2<=A+B+C:
  	ways2=(facts[A+B+C]*revfacts[i-2]*revfacts[A+B+C-(i-2)])%mod
  ways3=0
  if i>=1 and i-1<=A+C:
    ways3=(facts[A+C]*revfacts[i-1]*revfacts[A+C-(i-1)])%mod
  ways4=0
  if i>=1 and i-1<=A+B+C:
    ways4=(2*facts[A+B+C]*revfacts[i-1]*revfacts[A+B+C-(i-1)]-2*ways3)%mod
  ans.append((ways1+ways2+ways3+ways4)%mod)
for val in ans:
  print(val)

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

def inv(x):
  m = mod
  u = 1
  v = 0
  while m:
    t = x // m
    x -= t * m
    x, m = m, x
    u -= t * v
    u, v = v, u
  return u % mod

n = int(input())

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

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

two = -1
for i, c in enumerate(num):
  if c == 2:
    two = i
    break

l = -1
r = -1;
for i in range(n + 1):
  if l == -1 and a[i] == two:
    l = i
  elif l != -1 and a[i] == two:
    r = n - i

for k in range(1, n + 2):
  if k - 1 <= l + r:
    print((fac[n + 1] * inv(fac[k] * fac[n + 1 - k]) - fac[l + r] * inv(fac[k - 1] * fac[l + r - k + 1])) % mod)
  else:
    print(fac[n + 1] * inv(fac[k] * fac[n + 1 - k]) % mod)

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

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

def main():
    mod=10**9+7
    N=I()
    a=LI()
    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

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]
    
    for i in range(2, N + 5):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
        
    loc=[-1]*N
    mu=[-1,-1]
    for i in range(N+1):
        if loc[a[i]-1]==-1:
            loc[a[i]-1]=i
        else:
            mu[0]=loc[a[i]-1]
            mu[1]=i
    N1=mu[0]
    N2=N-mu[1]
    
    for i in range(N+1):
        if i==0:
            print(N)
        else:   
            print((cmb(N+1,i+1,mod)-cmb(N1+N2,i,mod))%mod)
        
            
    
            
            
        


main()

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


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


ans = [0] * (N + 2)
fN = fact[N + 1]
for i in range(1, N + 2):
    div = fact[i] * fact[N - i + 1] % mod
    value = fN * pow(div, mod - 2, mod) % mod
    ans[i] = value



x = Counter(A).most_common()[0][0]
left = A.index(x)
right = N - A.index(x, left + 1)
M = left + right

for i in range(0, M + 1):
    num = fact[M]
    div = fact[i] * fact[M - i] % mod
    comb = num * pow(div, mod - 2, mod) % mod
    ans[i + 1] = (ans[i + 1] - comb + mod) % mod

print(*ans[1:], sep="\n")

Solution (Python):
from collections import Counter


class Combination:
    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    N = int(input())
    A = tuple(map(int, input().split()))
    mod = 10 ** 9 + 7

    X = Counter(A).most_common()[0][0]
    left = A.index(X)
    right = A[::-1].index(X)
    LR = left + right

    comb = Combination(10 ** 5 + 10)

    ans = []
    for i in range(1, N + 2):
        val = comb(N+1, i)-comb(LR, i-1)
        val = (val + mod) % mod
        ans.append(val)

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

Solution (Python):
from collections import Counter

N = int(input())
A = tuple(map(int, input().split()))
mod = 10 ** 9 + 7

U = N + 10
fact = [1] * (U + 1)
inv = [1] * (U + 1)

for i in range(1, U + 1):
    fact[i] = fact[i - 1] * i % mod

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


def comb(N, r):
    if r < 0 or r > N:
        return 0
    res = fact[N] * inv[r] % mod
    res = res * inv[N - r] % mod
    return res


X = Counter(A).most_common()[0][0]
left = A.index(X)
right = A[::-1].index(X)
LR = left + right

for i in range(1, N + 2):
    ans = comb(N+1, i)-comb(LR, i-1)
    ans = (ans + mod) % mod
    print(ans)

Solution (Python):
from collections import Counter

U = 10**5+1
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
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
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
n = int(input())
A = list(map(int, input().split()))
x = Counter(A).most_common()[0][0]
left = A.index(x)
right = A[::-1].index(x)
for k in range(1, n+2):
  ans = comb(n+1, k) - comb(left+right, k-1)
  ans %= MOD
  print(ans)

Solution (Python):
from collections import Counter

U = 10**5+1
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
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
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
n = int(input())
A = list(map(int, input().split()))
x = Counter(A).most_common()[0][0]
left = A.index(x)
right = A[::-1].index(x)
print(n)
for k in range(2, n+2):
  ans = comb(n+1, k) - comb(left+right, k-1)
  ans %= MOD
  print(ans)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

def cmb(n, k):
    if k > n:
        return 0
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, 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

U = 10 ** 5 + 10 
fact, fact_inv = make_fact(U, MOD)

N = ir()
A = lr()
double = 0
used = set()
for i, a in enumerate(A):
    if a in used:
        double = a
        index_back = i
        break
    used.add(a)

index_front = A.index(double)
x = N + 1 - (index_back - index_front)
print(N)
for i in range(2, N+1):
    answer = cmb(N+1, i) - cmb(x-1, i-1)
    print(answer % MOD)

print(1)

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 = 10**6
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 )
N = int(input())
A = [int(c) for c in input().split()]
log = [0]*(N+1)
for i in range(N+1):
  if log[A[i]]!=0:
    j = i
  log[A[i]] = 1
c = A[j]
i = A.index(c)
m = i+N-j
for k in range(1,N+2):
  if m>=k-1:
    x = cmb(N+1,k,mod)-cmb(m,k-1,mod)
    print(x%mod)
  else:
    x = cmb(N+1,k,mod)
    print(x%mod)

Solution (Python):
class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
        self.inv[n] = pow(self.factorial[n],mod-2,mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i+1]*(i+1)%mod

    def comb(self,m,k):
        if m-k<0 or k<0: return 0
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod

MOD = 1000000007

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

F = Factorial(N+1,MOD)

tmp = [None for _ in range(N)]

for i in range(N+1):
    if tmp[A[i]-1] is None:
        tmp[A[i]-1] = i
    else:
        a = tmp[A[i]-1]
        b = i
        break

A = []

for i in range(1,N+2):
    A.append((F.comb(N-1,i)+F.comb(N-1,i-2)+F.comb(N-1,i-1)*2-F.comb(N+a-b,i-1))%MOD)

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

Solution (Python):
class Factorial:
    def __init__(self, n, mod=10**9+7):
        self.fac = [0] * (n+1)
        self.ifac = [0] * (n+1)
        self.fac[0] = 1
        self.ifac[0] = 1
        self.mod = mod
        modmod = self.mod - 2
        for i in range(n):
            self.fac[i+1] = self.fac[i] * (i+1) % self.mod
            self.ifac[i+1] = self.ifac[i] * pow(i+1, modmod, self.mod) % self.mod

    def comb(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        tmp =  self.ifac[n-r] * self.ifac[r] % self.mod
        return tmp * self.fac[n] % self.mod

    def perm(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        return (self.fac[n] * self.ifac[n-r]) % self.mod

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

d = {}
for i in range(0,n+1):
    if a[i] not in d:
        d[a[i]] = i
    else:
        l,r = d[a[i]], n-i
        break

fact = Factorial(n+1)

for i in range(1,n+2):
    ans = fact.comb(n+1,i)
    s = fact.comb(l+r,i-1)
    ans -= s
    while ans < 0:
        ans += mod
    print(ans)

Solution (Python):


def modmal(a,b,mod): 

    return a * b % mod




def moddiv(a,b,mod): 

    return (a * pow(b,mod-2,mod)) % mod




def inverse(a,mod): 
    return pow(a,mod-2,mod)







def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): 

    return fac[n] * inv[n-r] * inv[r] % mod


n = int(input())

dic = {}

a = list(map(int,input().split()))
twonum = None

for i in range(n+1):

    if a[i] not in dic:
        dic[a[i]] = [i]
    else:
        dic[a[i]].append(i)
        twonum = a[i]

mod = 10**9+7
fac,inv = modfac(n+10,mod)

for k in range(n+1):
    
    k += 1
    
    ans = modnCr(n+1,k,mod,fac,inv)

    l = dic[twonum][0]
    r = (n+1) - dic[twonum][1] - 1

    if l+r >= k-1:
        ans -= modnCr(l+r,k-1,mod,fac,inv)

    print (ans % mod)

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    c = collections.Counter(a)
    t = c.most_common()[0][0]
    pos = []
    for i in range(N+1):
        if a[i] == t:
            pos.append(i)
            
    l,r = pos
    MOD = 10**9+7
    fac = [0 for _ in range(N+2)]
    fac[0],fac[1] = 1,1
    inv = copy.deepcopy(fac)
    invfac = copy.deepcopy(fac)
    
    for i in range(2,N+2):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = MOD-(MOD//i)*inv[MOD%i]%MOD
        invfac[i] = (invfac[i-1]*inv[i])%MOD
        
    def coef(x,y):
        if x < y:
            return 0
        else:
            num = (((fac[x]*invfac[y])%MOD)*invfac[x-y]%MOD)
            return num
    
    for i in range(N+1):
        i += 1
        al = coef(N+1,i)
        dup = coef(N-r+l,i-1)
        print((al-dup)%MOD)


if __name__ == "__main__":
    main()

Solution (Python):


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


def div_mod(a, b, p):
    return (a * pow(b, p-2, p)) % p

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

def comb_mod(n, r, mod):
    if n < r:
        return 0
    return div_mod(div_mod(factorial_memo[n], factorial_memo[n-r], mod), factorial_memo[r], mod)


indices = [-1] * (n+1)
for i in range(n+1):
    if indices[a[i]] == -1:
        indices[a[i]] = i
    else:
        f_idx = indices[a[i]]
        s_idx = i
        break

for k in range(1, n+2):
    all_pattern = comb_mod(n+1, k, MOD)
    dup_pattern = comb_mod(f_idx + (n - s_idx), k-1, MOD)
    print((all_pattern - dup_pattern) % MOD)

Solution (Python):
import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x


fact = [1] * 100100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


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


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - n*(n+1)//2

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)