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):
n = 10**5+1
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

n = int(input())
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)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
N = int(input())
a = list(map(int, input().split()))
num = [[] for _ in range(N + 1)]
dnum = 0
mod = 10 ** 9 + 7
for i in range(N + 1):
  num[a[i]].append(i)
  if len(num[a[i]]) == 2:
    dnum = a[i]
class Factorial:
  def __init__(self, n, mod):
    self.f=[1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i=[pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(N + 1, mod)
for i in range(1, N + 2):
  t = f.combi(N + 1, i)
  u = 0
  if num[dnum][0] + (N + 1 - num[dnum][1]) >= i:
    u = f.combi(num[dnum][0] + (N + 1 - num[dnum][1]), i)
    if num[dnum][0] + (N + 1 - num[dnum][1] - 1) >= i:
      u -= f.combi(num[dnum][0] + (N + 1 - num[dnum][1] - 1), i)
  print((t - u) % mod)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = list(map(int,input().split()))
    
    
    
    mod = 10**9 + 7
    ex = [1]
    for i in range(1,10**5+1):
        ex.append((ex[-1]*i)%mod)
        
    def comb(n,k):
        if 0 <= n and 0 <= k <= n:
            return (ex[n] * pow(ex[k],mod-2,mod) * pow(ex[n-k],mod-2,mod))%mod
        else:
            return 0
    
    D = {}
    for i in range(N+1):
        if not A[i] in D:
            D[A[i]] = i
        else:
            double = A[i]
            d1 = D[A[i]]
            d2 = i
    A = d1
    B = d2-d1-1
    C = N-d2
    
    for i in range(1,N+2):
        ans = 0
        ans += comb(A+B+C,i)
        ans += 2*comb(A+B+C,i-1)
        ans -= comb(A+C,i-1)
        ans += comb(A+B+C,i-2)
        
        print(ans%mod)
        
        
    
    
main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n,k = LI()
    a = LI()
    d = defaultdict(lambda:0)
    for i in a:
        d[i] += 1
    d = list(d.values())
    d.sort()
    ans = 0
    for i in range(len(d)-k):
        ans += d[i]
    print(ans)
    return


def B():
    n,z,w = LI()
    a = LI()
    if n == 1:
        print(abs(a[0]-w))
        return
    ans = max(abs(a[-1]-w),abs(a[-2]-a[-1]))
    print(ans)
    return


def C():
    n = I()
    s1 = S()
    s2 = S()
    dp = [[[0]*3 for j in range(3)] for i in range(n+1)]
    if s1[0] == s2[0]:
        dp[1] = [[1 if i == j else 0 for j in range(3)] for i in range(3)]
    else:
        dp[1] = [[0 if i == j else 1 for j in range(3)] for i in range(3)]
    for i in range(1,n):
        ni = i+1
        if s1[i] == s2[i]:
            for j in range(3):
                for k in range(3):
                    if k == j:continue
                    for l in range(3):
                        if l == j:continue
                        dp[ni][j][j] += dp[i][k][l]
        else:
            if i and s1[i] == s1[i-1]:
                for j in range(3):
                    for k in range(3):
                        dp[ni][j][k] = dp[i][j][k]
            else:
                for j in range(3):
                    for k in range(3):
                        if k == j:continue
                        for l in range(3):
                            if l == j:continue
                            for m in range(3):
                                if m == k:continue
                                dp[ni][j][k] += dp[i][l][m]
    ans = 0
    for i in range(3):
        for j in range(3):
            ans += dp[n][i][j]
    print(ans%mod)
    return


def D():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod
    n = I()
    a = LI()
    d = defaultdict(lambda : 0)
    for i in range(n+1):
        if d[a[i]]:
            l = d[a[i]]-1
            r = n-i
            break
        d[a[i]] = i+1
    fact = [1]
    m = 100001
    for i in range(m):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(m+1)
    inv[m] = pow(fact[m],mod-2,mod)
    for i in range(m)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    for i in range(1,n+2):
        ans = comb(n+1,i)
        if l+r >= i-1:
            ans -= comb(l+r,i-1)
            ans %= mod
        print(ans)
    return


def E():

    return


if __name__ == "__main__":
    D()

Solution (Python):
from collections import Counter
N = int(input())

A = list(map(int, input().split()))
c = Counter(A)
s = c.most_common()[0][0]
idx_s = [i for i,x in enumerate(A) if x == s]
l = idx_s[0]
r = idx_s[1]

MOD = 10**9+7
fac = [1,1] + [0]*N
finv = [1,1] + [0]*N
inv = [0,1] + [0]*N
for i in range(2,N+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

for i in range(1,N+2):
    print((nCr(N+1, i) - nCr(l+N+1-(r+1), i-1)) % MOD)

Solution (Python):

mod = 10**9+7
n = int(input())
a = list(map(int, input().split()))
check = [-1]*(n+1)
def make_fact(n):
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact

def make_fact_inv(n):
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact = make_fact(n+1)
fact_inv = make_fact_inv(n+1)
def comb(n, k):
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod

for i, ai in enumerate(a):
    if check[ai]<0:
        check[ai] = i
    else:
        b = check[ai]
        c = i
        break
m = c-b-1
for k in range(1, n+2):
    if n-m-1>=k-1:
        print((comb(n+1, k)-comb(n-m-1, k-1))%mod)
    else:
        print(comb(n+1, k))

Solution (Python):
from collections import Counter

def factorials(n,m):
    
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i%m)

    
    g = [1]
    for i in range(n):
        g.append(pow(f[i+1],m-2,m))

    return f,g


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

m = 10**9+7

f,g = factorials(n,m)

counter = Counter(a)

for x in a:
    if counter[x] == 2:
        b = x
        break

l,r = [i for i, x in enumerate(a) if x == b]

if r-l == 1:
    renzoku = True
else:
    renzoku = False

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

if renzoku:
    print(n)
    for k in range(2,n):
        x = f[n-1]*g[n-k-1]*g[k]
        y = f[n-1]*g[n-k]*g[k-1]
        z = f[n-1]*g[n-k+1]*g[k-2]
        print((x+y+z)%m)
    print(n)
    print(1)
else:
    print(n)
    for k in range(2,n):
        x = f[n-1]*g[n-k-1]*g[k]
        y = f[n-1]*g[n-k]*g[k-1] * 2
        z = f[n-1]*g[n-k+1]*g[k-2]
        if n-r + l >=k-1:
            y -= f[n-r+l]*g[n-r+l-k+1]*g[k-1]
        print((x+y+z)%m)
    print(n+1)
    print(1)

Solution (Python):
fact=[1]
MOD=10**9+7
temp=1
for i in range(1,10**6):
    temp*=i
    temp%=MOD
    fact+=[temp]

def bi(a,b):
    if b>a:
        return 0
    up=fact[a]
    down=fact[a-b]*fact[b]
    down=pow(down,MOD-2,MOD)
    return (up*down)%MOD
    
def find(A):
    n=len(A)-1
    dic={}
    for i in range(len(A)):
        if A[i] in dic:
            dic[A[i]]+=[i]
        else:
            dic[A[i]]=[i]
    bad=[]
    for x in dic:
        if len(dic[x])==2:
            bad=dic[x][:]
            break
    p1=bad[0]
    p2=n-bad[1]
    ans=[]
    ans+=[n]
    for k in range(2,n+1):
        ans+=[(bi(n+1,k)-bi(p1+p2,k-1))%MOD]
    ans+=[1]
    return ans

input()
A=list(map(int,input().strip().split(' ')))
for x in find(A):
    print(x)

Solution (Python):
from itertools import accumulate
from operator import mul


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

MOD = 10**9 + 7



class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


f = [ModInt(1)] + list(
    accumulate(
        map(ModInt, range(1, n + 2)),
        mul
    )
)


def c(n, k):
    return (
        0 if n < k else
        f[n] / (f[n - k] * f[k])
    )


w = sum(a) - n * (n + 1) // 2
m = a.index(w) + a[::-1].index(w)
ans = '\n'.join(
    str(c(n + 1, k) - c(m, k - 1))
    for k in range(1, n + 2)
)


print(ans)

Solution (Python):



import sys


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        if n < r:
            return 0
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret



sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

already = set()
for i, l in enumerate(A):
    if l in already:
        dup_ind = i
        dup_num = l
        break
    else:
        already.add(l)

mid_dup = dup_ind-A.index(dup_num)+1

F = FactMod(n+1, MOD)


for k in range(1, n+2):
    all_pattern = F.comb(N, k)
    rem_pattern = F.comb(N-mid_dup, k-1)
    print((all_pattern-rem_pattern+MOD) % MOD)

Solution (Python):



import sys


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret



sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
N = n+1
A = list(map(int, input().split()))
MOD = 10**9+7
already = set()
for i, l in enumerate(A):
    if l in already:
        dup_ind = i
        dup_num = l
        break
    else:
        already.add(l)
before_first_dup_num = A.index(dup_num)
after_dup_num = N-dup_ind-1

F = FactMod(n+1, MOD)
for k in range(1, n+2):
    all_pattern = F.comb(N, k)
    rem_pattern = F.comb(before_first_dup_num+after_dup_num,
                         k-1) if before_first_dup_num+after_dup_num >= k-1 else 0
    print((all_pattern-rem_pattern+MOD) % MOD)

Solution (Python):
class BinomialCoefficient:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}                
        self.inverse = {i: None for i in range(1, N+1)}      
        self.fact_inverse = {i: None for i in range(N+1)} 
        
        
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def binom(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dup_num = sum(A) - N*(N+1)//2
dup_num_idx = sorted([i+1 for i, a in enumerate(A) if a == dup_num])
l, r = dup_num_idx[0], dup_num_idx[1]

bc = BinomialCoefficient(N+1, MOD)
for k in range(1, N+2):
    print((bc.binom(N+1, k) - bc.binom(N+1 - (r - l + 1), k - 1)) % MOD)

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


def ex_euclid(a,b,c,d):
    if (b == 1) : return d
    x = a // b
    y = a % b
    return ex_euclid(b,y,d,(c[0]-x*d[0],c[1]-x*d[1]))
    

def mod_inv(a,p):
    x = ex_euclid(p,a,(1,0),(0,1))
    return x[1] % p

n = int(input())
visited = [-1 for i in range(n+1)]

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

for i in range(n+1):
    if(visited[a[i]] == -1):visited[a[i]] = i
    else : 
        x = visited[a[i]]
        y = i
        break

m = x + (n-y)



nc = n+1
mc = 1

print(nc-mc)

for i in range(2,n+2):
    nc = (nc * (n+2-i)) % MOD
    nc = (nc * mod_inv(i,MOD)) % MOD
    if (i-1 <= m):
        mc = (mc * (m+2-i)) % MOD
        mc = (mc * mod_inv(i-1,MOD)) % MOD
        print((nc - mc) % MOD)
    else:
        print(nc)

Solution (Python):

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import Counter
mod=10**9+7
n=int(input())
A=list(map(int,input().split()))
factorial=[1]
for i in range(1,n+2):
    factorial.append(factorial[i-1]*i%mod)
inverse=[0]*(n+2)
inverse[n+1]=pow(factorial[n+1],mod-2,mod)
for i in range(n,-1,-1):
    inverse[i]=inverse[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod
C=Counter(A)
i=C.most_common()[0][0]
idx=[k for k, x in enumerate(A) if x==i]
for k in range(1,n+2):
    print((comb(n+1,k)-comb(n+idx[0]-idx[1],k-1))%mod)

Solution (Python):
N=int(input())
a=[int(i)-1 for i in input().split()]
count=[0]*N
for i in range(N+1):
  count[a[i]]+=1
  if count[a[i]]==2:
    D=a[i]
    break
flag=False
k=0
mod=10**9+7
for i in range(N+1):
  if a[i]==D and not flag:
    flag=True
  elif a[i]==D and flag:
    break
  elif flag:
    k+=1
    
Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
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

inverseFactorial=[1]*(N+1)
inverseFactorial[N]=power(Factorial[N],mod-2)
for i in range(0,N)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod

dp=[[0]*3 for i in range(N+2)]
dp[0][0]=1

for i in range(N+1):
  dp[i+1][0]=comb(N-1,i+1)
  dp[i+1][1]=-comb(N-k-1,i)+2*dp[i][0]
  if i>=1:
    dp[i+1][2]=dp[i-1][0]
  print(sum(dp[i+1])%mod)

Solution (Python):




























import sys
input = sys.stdin.readline

n = int(input())
A = tuple(map(int,input().split()))
p = 10**9+7
used = [-1]*n
for i in range(n+1):
    if used[A[i]-1]>=0:
        a = used[A[i]-1]
        b = i
        break
    used[A[i]-1] = i



def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    
    return [w[0],w[1]]


def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m







fact = [1]
k = 1
for i in range(1,n+2):
    k = k*i%p
    fact.append(k)



def mod_e(n,p):
    res = 0
    while n >= p:
        res += n//p
        n = n//p
    return res


def mod_fact(n,p):
    if n==0:
        return 1
    
    
    res = mod_fact(n//p,p)
    
    if n//p %2 != 0:
        return res*(p-fact[n%p])%p
    return res*fact[n%p]%p
    



def mod_comb(n,k,p):
    if n < 0 or k < 0 or n<k:
        return 0
    e1 = mod_e(n,p)
    e2 = mod_e(k,p)
    e3 = mod_e(n-k,p)
    
    if e1 > e2 + e3:
        return 0

    
    a1 = mod_fact(n,p)
    a2 = mod_fact(k,p)
    a3 = mod_fact(n-k,p)
    return a1 * mod_inv(a2*a3%p,p) %p

for i in range(1,n+2):
    res = mod_comb(n+1,i,p)-mod_comb(a+n-b,i-1,p)
    if res < 0:
        res += p
    print(res)

Solution (Python):
from collections import Counter
mod=10**9+7
N=10**5+11
fac,finv,inv = [0]*N,[0]*N,[0]*N
 
def cmb_init():
        fac[0]=fac[1]=finv[0]=finv[1]=inv[1]=1
        for i in range(2,N):
                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 cmb_mod(n,k):
        if n<k : return 0
        return fac[n]*(finv[k]*finv[n-k]%mod)%mod
 
n=int(input())
a=list(map(int,input().split()))
ac = Counter(a).most_common()[0][0]
sames=[i for i,x in enumerate(a) if x==ac]
same_len = sames[0]+(n-sames[1])
cmb_init()
print(n)
 
for i in range(1,n):
        nums = cmb_mod(n+1,i+1) - cmb_mod(same_len,i)
        if nums < 0: nums+=mod
        print(nums)
print(1)

Solution (Python):
N = int(input())
L = [-1] * N
a = [int(i)-1 for i in input().split()]
for i in range(N+1):
    if L[a[i]] == -1:
        L[a[i]] = i
    else:
        x1, x2 = (min(L[a[i]], i), max(L[a[i]], i))
A = x1
B = x2-x1-1
C = N-x2

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007



fac_lim = N
fac = [None]*(fac_lim+1)
fac[0] = 1
for i in range(fac_lim):
    fac[i+1] = fac[i] * (i+1)
    fac[i+1] = fac[i + 1] % 1000000007

fac_inv = [None]*(fac_lim+1)
fac_inv[fac_lim] = power(fac[fac_lim], 1000000005)
for i in range(fac_lim, 0, -1):
    fac_inv[i-1] = (fac_inv[i] * i)  % 1000000007

def conv(a, b):
    if a >= b:
        return (fac[a] * fac_inv[a-b] * fac_inv[b]) % 1000000007
    else:
        return 0

N1_conv = [0]*(N+2)
AC_conv = [0]*(N+2)
for i in range(N+2):
    N1_conv[i] = conv(N-1, i)
for i in range(N+2):
    AC_conv[i] = conv(A+C, i)
for K in range(1, N+2):
    ans = 0
    ans += N1_conv[K]
    if K>0:
        ans += AC_conv[K-1]
        ans += 2 * N1_conv[K-1]
        ans -= 2 * AC_conv[K-1]
    if K>1:
        ans += N1_conv[K-2]
    ans %= 1000000007
    print(ans)

Solution (Python):
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]

n = int(input())
a = ai()

dup = sum(a)-n*(n+1)//2
ant = a.index(dup)
post = a[::-1].index(dup)

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

inverse = [0]*(n+2)
inverse[n+2-1] = pow(factorial[n+2-1], mod-2,mod)
for i in range(n+2-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % 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 k in range(1,n+2):
    if k == 1:
        print(n)
    else:
        ans = nCr(n+1,k) - nCr(ant+post,k-1)
        if ans < 0:
            ans += mod
        print(ans)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
mod = 10**9 +7
n = int(input())

fac = [1 for _ in range(n+1)]
for i in range(n):
    fac[i+1] = (i+1)*fac[i]%mod

inv = [1 for _ in range(n+1)]
for i in range(2,n):
    inv[i] = (-(mod//i) * inv[mod%i]) %mod    

facinv = [1 for _ in range(n+1)]
for i in range(n):
    facinv[i+1] = inv[i+1]*facinv[i]%mod

def comb(a, b):
    if a < b or b < 0:
        return 0
    return fac[a]*facinv[b]*facinv[a-b]
    
a = inpl()
x = sum(a) - n*(n+1)//2
Y = [i for i, v in enumerate(a) if v == x]
y = n-Y[1]+Y[0]

for k in range(1,n+2):
    ans = (comb(n-1, k) + 2*comb(n-1, k-1) + comb(n-1, k-2) - comb(y, k-1))%mod
    print(ans)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
mod = 10**9 +7
n = int(input())

fac = [1 for _ in range(n+1)]
for i in range(n):
    fac[i+1] = (i+1)*fac[i]%mod

inv = [1 for _ in range(n+1)]
for i in range(2,n):
    inv[i] = (-(mod//i) * inv[mod%i]) %mod    

facinv = [1 for _ in range(n+1)]
for i in range(n):
    facinv[i+1] = inv[i+1]*facinv[i]%mod

def comb(a, b):
    if a < b or b < 0:
        return 0
    return fac[a]*facinv[b]*facinv[a-b]
    
a = inpl()
x = sum(a) - n*(n+1)//2
Y = [i for i, v in enumerate(a) if v == x]
y = n-Y[1]+Y[0]

for k in range(1,n+2):
    ans = (comb(n-1, k) + 2*comb(n-1, k-1) + comb(n-1, k-2) - comb(y, k-1))%mod
    print(ans)

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

fact = {i: None for i in range(n+2)}                 
inverse = {i: None for i in range(1, n+2)}       
fact_inverse = {i: None for i in range(n+2)}  

fact[0] = fact[1] = 1
fact_inverse[0] = fact_inverse[1] = 1
inverse[1] = 1
for i in range(2, n+2):
    fact[i] = i * fact[i-1] % MOD
    inverse[i] = - inverse[MOD % i] * (MOD // i) % MOD
    fact_inverse[i] = inverse[i] * fact_inverse[i-1] % MOD

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

dup_num = sum(A) - n*(n+1)//2
dup_idx = []
for i, a in enumerate(A):
    if a == dup_num:
        dup_idx.append(i)
        
left, right = dup_idx[0], dup_idx[1]
        
for k in range(1, n+2):
    print((combination(n+1, k) - combination(n + 1 - (right - left + 1), k - 1)) % MOD)

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

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())



def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       

def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac


def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        

def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod

from collections import Counter

n = ni()
a = list(li())

cnt = Counter(a)
two = cnt.most_common(1)[0][0]

left = a.index(two)
right = a[::-1].index(two)


MOD = 10**9+7

inv = inv_mod(n+2,MOD)
fac = fact(n+2,MOD)
fac_inv = fact_inv(n+2,inv,MOD)

for i in range(1,n+2):
    if 1 < i < n+1:
        ans = nCr(n+1,i,MOD,fac,fac_inv)

        if left+right >= i-1:
            ans -= nCr(left+right,i-1,MOD,fac,fac_inv)
            
        if ans < 0:
            ans += MOD
            
        print(ans)
        
    elif i == 1:
        print(n)
    else:
        print(1)

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

ctr = Counter(A)
doub = ctr.most_common()[0][0]
i1 = A.index(doub)
i2 = N - A[::-1].index(doub)
l = N - (i2-i1)

fac = [1,1] + [0]*N
finv = [1,1] + [0]*N
inv = [0,1] + [0]*N
for i in range(2,N+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

ans = []
for n in range(1,N+2):
    ans.append(ncr(N+1,n))
for i in range(l+1):
    ans[i] -= ncr(l,i)
    ans[i] %= MOD

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

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

MOD = 10**9 + 7
 
N = read()
A = reads()

fact = [1] * N
for i in range(1, N):
  fact[i] = (fact[i-1] * i) % MOD 
invfact = [0] * N; invfact[-1] = pow(fact[-1], MOD-2, MOD)
for i in range(N-2, -1, -1):
  invfact[i] = invfact[i+1] * (i+1) % MOD
def comb(n, k):
  return fact[n] * invfact[n-k] * invfact[k] % MOD  

cnt = Counter(A)
q = next(i for i in range(1,N+1) if cnt[i] == 2)
i1 = A.index(q); i2 = A.index(q, i1+1)
m = N - (i2 - i1)


print(N)
for k in range(2, N+1):
  ans = comb(N-1, k-1) * 2 + comb(N-1, k-2)
  if m >= k-1:
    ans -= comb(m, k-1)
  if k <= N-1:
    ans += comb(N-1, k)
  print(ans % MOD)
print(1)

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
deni=[1]*(N+1)
quot=[1]*(N+1)
for i in range(1,N+1):
    deni[i]=(deni[i-1]*(i+1))%mod
for i in range(1,N+1):
    t=pow(i+1,mod-2,mod)
    quot[i]=(quot[i-1]*t)%mod
deni=[1]+deni
quot=[1]+quot
box=[[0,0]]*(N+1)
for i in range(N+1):
    if box[A[i]-1][0]==1:
        k_1=box[A[i]-1][1]
        k_2=N-i
        break
    box[A[i]-1]=[1,i]
K=k_1+k_2
ans =[]
for k in range(1,N+2):
    if k==1:
        ans.append(N)
    elif K>=k-1:
        s=deni[N+1]
        s=(s*quot[k])%mod
        s=(s*quot[N+1-k])%mod
        t=deni[K]
        t=(t*quot[k-1])%mod
        t=(t*quot[K-k+1])%mod
        
        ans.append((s-t)%mod)
    else:
        s=deni[N+1]
        s=(s*quot[k])%mod
        s=(s*quot[N-k+1])%mod
        
        ans.append(s)

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

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

f_list = [1] * 100001
f_r_list = [1] * 100001

for i in range(100000):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, 100002):
	f_r_list[-i] = int((f_r_list[-i + 1] * (100003 - i)) % MOD)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

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


doubled = sum(a) - n * (n + 1) / 2
x = a.index(doubled)
y = a_r.index(doubled)
num = x + y

print(n)

for i in range(2, n + 2):
	if num >= i - 1:
		print(int((comb(n + 1, i) - comb(num, i - 1)) % MOD))
	else:
		print(comb(n + 1, i))