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):
MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self//value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

class Combination:
    def __init__(self,max_n):
        self.max_n=0
        self.fact=[Fp(1)]
        self.ifact=[Fp(1)]
        self.make_fact_list(max_n)
    def C(self,n,k):return self.fact[n]*self.ifact[k]*self.ifact[n-k] if 0<=k<=n else 0
    def H(self,n,k):return self.C(n+k-1,k) if n or k else 1
    def P(self,n,k):return self.fact[n]*self.ifact[n-k] if 0<=k<=n else 0
    def make_fact_list(self,max_n):
        if max_n<=self.max_n: return
        self.fact+=[Fp(0)]*(max_n-self.max_n)
        self.ifact+=[Fp(0)]*(max_n-self.max_n)
        for i in range(self.max_n+1,max_n+1):
            self.fact[i]=self.fact[i-1]*i
            self.ifact[i]=self.ifact[i-1]//i
        self.max_n=max_n

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

L = B[a]
R = N - i
M = i - B[a] - 2
print(N)
comb = Combination(N+1)
for k in range(2, N+2):
    print(comb.C(N+1, k) - comb.C(L + R, k-1))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
a = LIST()

check = [0]*(n+1)

kaburi = 0
idx1 = 0
idx2 = 0

mod = 10**9 + 7
N = 10**6  
factorial = [1]
for i in range(1, N):
    factorial.append(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, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod
def C(n, r):
    return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod
x_inv = [0] * (N)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(N-2, -1, -1):
    x_inv[i] = x_inv[i+1] * (i+1) % mod

for i in range(n+1):
	if check[a[i]]:
		kaburi = a[i]
		idx1 = check[a[i]]
		idx2 = i + 1
		break
	check[a[i]] = i + 1



l = idx1-1
r = n-idx2+1
idx1 -= 1
idx2 -= 1

thre = n-(idx2-idx1)+2


for k in range(1, n+2):
	if k >= thre:
		print(C(n+1, k)%mod)
	else:
		print((C(n+1, k)-C(r+l, k-1))%mod)

Solution (Python):
def build_combination(n, mod):
    def cmb(n, r):
        if r < 0 or n < r:
            return 0
        return (((invs[r] * invs[n - r]) % mod) * fact[n]) % mod

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

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

    return cmb


def find(a):
    """重複する数値のindexのペアを返す"""
    n = len(a)
    checked = [-1] * (n + 1)
    for i, x in enumerate(a):
        if checked[x] != -1:
            return checked[x], i
        else:
            checked[x] = i
    raise ValueError


def main():
    mod = 10 ** 9 + 7

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

    cmb = build_combination(n + 1, mod)

    li, ri = find(a)

    for k in range(1, n + 2):
        ret = (cmb(n + 1, k) - cmb(n + 1 - (ri - li + 1), k - 1)) % mod  
        print(ret)
        
        
        
        


if __name__ == '__main__':
    main()

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

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

mod = 10**9+7 
N = 10**5+1
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()))
v=[-1]*n
for i,a in enumerate(A):
    
    if v[a-1]!=-1:
        s=v[a-1]
        f=i
    if v[a-1]==-1:
        v[a-1]=i


mod=10**9+7
for i in range(1,n+1):
    sousuu=cmb(n+1,i,mod)
    tyouhuku=cmb(s+n-f,i-1,mod)
    """if i==1:
        sousuu=n+1
        tyouhuku=1
    else:
        sousuu*=(n+2-i)
        sousuu//=i
        tyouhuku*=(s+n-f+1-i+1)
        tyouhuku//=(i-1)"""
    
    print((sousuu-tyouhuku)%mod)
print(1)

Solution (Python):
from collections import Counter

mod = 10**9+7
rng = 100002
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<=0 or k<0 or n<k:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod

n = int(input())
a = list(map(int,input().split()))
same = []
c = Counter(a)
x = c.most_common()[0][0]
for i in range(n+1):
  if a[i] == x:
    same.append(i+1)
y = same[1]-same[0]+1
print(n)
for k in range(2,n+2):
  print((cmb(n+1,k)-cmb(n+1-y,k-1))%mod)

Solution (Python):

import sys
from collections import Counter 
MOD = 1000000007 


def solve(n: int, a: "List[int]"):
    counter = Counter(a).most_common()
    twiceValue = counter[0][0]
    first_index = None
    second_index = None

    for i in range(n+1):
        if a[i] == twiceValue:
            if first_index == None:
                first_index = i
            else:
                second_index = i

    
    left = first_index

    
    right = n-second_index
    edge = left+right

    
    combination_table = {n+1: [0]*(n+2), edge: [0]*(edge+1)}
    
    combination_table[n+1][0] = 1
    combination_table[n+1][n+1] = 1
    combination_table[edge][0] = 1
    combination_table[edge][edge] = 1
    c_value = 1

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

    c_value = 1
    
    for i in range(1,edge):
        c_value *= (edge + 1 - i) * pow(i,MOD-2,MOD)
        c_value %= MOD
        combination_table[edge][i] = c_value

    for i in range(1,n+2):
        if i-1 <= edge:
            value = combination_table[n+1][i] - combination_table[edge][i-1]
        else:
            value = combination_table[n+1][i]
        print(value%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(n + 1)]  
    solve(n, a)

if __name__ == '__main__':
    main()

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**5+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()))
a=sum(A)-n*(n+1)//2
B=[]
for i in range(n+1):
  if A[i]==a:
    B.append(i)
for k in range(1,n+2):
  print((cmb(n-1,k,mod)+2*cmb(n-1,k-1,mod)-cmb(n-B[1]+B[0],k-1,mod)+cmb(n-1,k-2,mod))%mod)

Solution (Python):
n = int(input())
a = [int(x) for x in input().split()]

mod = 10**9 + 7


class Comb(object):
    def __init__(self, N, mod=10**9 + 7):
        self.mod = mod
        self.fac, self.inv = [1] * (N + 1), [1] * (N + 1)
        for i in range(2, N + 1):
            self.fac[i] = self.fac[i - 1] * i % mod
            self.inv[i] = self.inv[i - 1] * pow(i, mod - 2, mod) % mod

    def calc(self, n, k):
        if n >= k:
            return self.fac[n] * self.inv[k] * self.inv[n - k]
        else:
            return 0


c = [0] * (n + 1)
indexes = [[] for _ in range(n+1)]
for i in range(n + 1):
    c[a[i]] += 1
    indexes[a[i]].append(i)
    if c[a[i]] == 2:
        indexes = indexes[a[i]]
        break

m = indexes[0] + (n - indexes[1])
comb = Comb(n + 1)
for k in range(1, n + 2):
    x = comb.calc(n + 1, k)
    y = comb.calc(m, k - 1)
    ans = (x - y) % mod
    print(ans)

Solution (Python):


import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        
        inverse = [1] * MAX
        
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        
        r = min(r, n-r)
        
        numerator = self.fact[n]
        
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

N = INT()
A = LIST()


dup = 0
for k, v in Counter(A).items():
    if v == 2:
        dup = k
        break
st = []
for i, a in enumerate(A):
    if a == dup:
        st.append(i)

M = N - (st[1] - st[0])

mt = ModTools(N+1, MOD)
for i in range(N+1):
    
    ans = mt.nCr(N+1, i+1) - mt.nCr(M, i)
    print(ans % MOD)

Solution (Python):
import collections

mod = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod


def perm(n, k):
  return fact[n] * rfact[n-k] % mod


def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod
already = [0] * (n+1)
k = 0
for key,v in enumerate(a):
  if already[v]:
    k = already[v] + n - key - 1
    break
  else:
    already[v] = key+1
for i in range(n+1):
  if i == n:
    print(1)
    exit()
  ans = comb(n,i) + comb(n,i+1)
  if i <= k:
    ans -= comb(k,i)
  ans %= mod
  print(ans)

Solution (Python):
import collections

mod = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod


def perm(n, k):
  return fact[n] * rfact[n-k] % mod


def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod
already = [0] * (n+1)
k = 0
for key,v in enumerate(a):
  if already[v]:
    k = already[v] + n - key - 1
    break
  else:
    already[v] = key+1
for i in range(n+1):
  if i == n:
    print(1)
    exit()
  ans = comb(n,i) + comb(n,i+1)
  if i <= k:
    ans -= comb(k,i)
  ans %= mod
  print(ans)

Solution (Python):


class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [-1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod
        

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod


def main():
    MOD = 10 ** 9 + 7

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

    pos = [-1] * (N + 1)
    indices = None
    for i, a in enumerate(A):
        if pos[a] == -1:
            pos[a] = i
        else:
            indices = pos[a], i
            break

    width = indices[1] - indices[0] + 1
    

    calc = Calc(max_value=N + 1, mod=MOD)

    for k in range(1, N + 1 + 1):
        res = (calc.combination(N + 1, k) - calc.combination(N + 1 - width, k - 1)) % MOD
        print(res)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 1000000007

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

MOD = 10**9+7 
MAX_N = 10**5+10
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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






def solve():
  N = int(input())
  A = list(map(int, input().split()))
  counter = [-1]*(N+2)
  multi_num = -1
  left_element_num = -1
  right_element_num = -1
  for i, a_i in enumerate(A):
    if counter[a_i] != -1:
      left_element_num = counter[a_i]
      right_element_num = N-i
      break
    else:
      counter[a_i] = i

  
  output = []
  for i in range(1, N+2):
    if i == 1:
      output.append(str(N))
      
    elif i == N+1:
      output.append(str(1))
      
    else:
      ret = cmb(N+1, i)%MOD
      ret = (ret-cmb(left_element_num+right_element_num, i-1)%MOD)%MOD
      output.append(str(ret))
  
  print('\n'.join(output))
  
solve()

Solution (Python):
import sys

MOD = 10 ** 9 + 7

def make_table(n=10**5+1, p=10**9+7):
    fac = [None] * (n + 1)
    fac[0] = 1
    ifac = fac.copy()
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % p
    ifac[n] = pow(fac[n], p - 2, p)
    for i in range(n-1, 0, -1):
        ifac[i] = ifac[i+1] * (i + 1) % p
    return fac, ifac
fac, ifac = make_table()
def comb_mod(n, r, mod=10**9+7):
    if r < 0 or r > n:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

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

def main():
    appeared = [False] * (n + 1)
    for i in range(n+1):
        cur = a[i] 
        if appeared[cur]:
            x1, x2 = appeared[cur], i+1
            break
        appeared[cur] = i+1
    
    res = [0] * (n + 2)
    for i in range(1, n+2):
        res[i] += comb_mod(n+1, i)

    x = (x1 - 1) + (n + 1 - x2)
    for i in range(x+1):
        res[i+1] -= comb_mod(x, i)
        res[i+1] %= MOD

    return res[1:]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Solution (Python):
import sys

MOD = 10 ** 9 + 7

def make_table(n=10**5+1, p=10**9+7):
    fac = [None] * (n + 1)
    fac[0] = 1
    ifac = fac.copy()
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % p
    ifac[n] = pow(fac[n], p - 2, p)
    for i in range(n-1, 0, -1):
        ifac[i] = ifac[i+1] * (i + 1) % p
    return fac, ifac
fac, ifac = make_table()
def comb_mod(n, r, mod=10**9+7):
    if r < 0 or r > n:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

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

def main():
    appeared = [False] * (n + 1)
    for i in range(n+1):
        cur = a[i] 
        if appeared[cur]:
            x1, x2 = appeared[cur], i+1
            break
        appeared[cur] = i+1
    
    res = [0] * (n + 2)
    for i in range(1, n+2):
        res[i] += comb_mod(n+1, i)
        res[i] %= MOD
    x = (x1 - 1) + (n + 1 - x2)
    
    for i in range(x+1):
        res[i+1] -= comb_mod(x, i)
        res[i+1] %= MOD

    return res[1:]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Solution (Python):
class ModWorld:
    def __init__(self, mod):
        self.mod = mod

    def prepare_factorial(self, N):
        self.f = [1]*(N+1) 
        p = 1
        for i in range(1,N+1):
            p = (p*i) % self.mod
            self.f[i] = p
            
        self.finv = [None]*(N+1)
        for i, s in enumerate(self.f):
            self.finv[i] = self.modpow(s, -1)

    def modpow(self, x, k):
        x %= self.mod
        k %= self.mod-1 
        retval = 1
        while k:
            if k&1: retval = retval*x % self.mod
            k>>=1
            x = x*x % self.mod

        return retval

    def modcomb(self, n, k):
        return self.f[n] * self.finv[n-k] * self.finv[k] % self.mod

mw = ModWorld(mod=10**9+7)
mw.prepare_factorial(N=10**5+10)

n = int(input())
A = list(map(int, input().split()))
P = [None]*(n+1)
for i, a in enumerate(A):
    if P[a] is not None: break
    P[a] = i
m = i-P[a]+1

for k in range(1, n+2):
    ans = mw.modcomb(n+1, k)
    if k-1<=n+1-m : ans -= mw.modcomb(n+1-m, k-1)
    print(ans%mw.mod)

Solution (Python):
from collections import Counter

n, *a = map(int, open(0).read().split())
n += 1


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


def make_table(n, mod=10 ** 9 + 7):
    N = n
    
    g1 = [0] * (N + 1)
    g1[0] = 1
    g1[1] = 1

    
    g2 = [0] * (N + 1)
    g2[0] = 1
    g2[1] = 1

    
    inverse = [0] * (N + 1)
    inverse[0] = 0
    inverse[1] = 1

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

    return tuple(g1), tuple(g2), tuple(inverse)


d = Counter(a).most_common(1)[0][0]
lr = [i for i, e in enumerate(a) if e == d]
l = lr[1] - lr[0] + 1
g1, g2, inverse = make_table(n)
MOD = 10 ** 9 + 7

answer = [(cmb(n, i, MOD) - cmb(n - l, i - 1, MOD)) % MOD for i in range(1, n + 1)]
print('\n'.join(map(str, answer)))

Solution (Python):
from collections import Counter

n, *a = map(int, open(0).read().split())
n += 1


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


def make_table(n, mod=10 ** 9 + 7):
    N = n
    
    g1 = [0] * (N + 1)
    g1[0] = 1
    g1[1] = 1

    
    g2 = [0] * (N + 1)
    g2[0] = 1
    g2[1] = 1

    
    inverse = [0] * (N + 1)
    inverse[0] = 0
    inverse[1] = 1

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

    return tuple(g1), tuple(g2), tuple(inverse)


d = Counter(a).most_common(1)[0][0]
lr = [i for i, e in enumerate(a) if e == d]
l = lr[1] - lr[0] + 1
g1, g2, inverse = make_table(n)
MOD = 10 ** 9 + 7

answer = [(cmb(n, i) - cmb(n - l, i - 1)) % MOD for i in range(1, n + 1)]
print('\n'.join(map(str, answer)))

Solution (Python):
from collections import Counter

n, *a = map(int, open(0).read().split())
n += 1


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


def make_table(n, mod=10 ** 9 + 7):
    mod = mod
    N = n
    
    g1 = [0] * (N + 1)
    g1[0] = 1
    g1[1] = 1

    
    g2 = [0] * (N + 1)
    g2[0] = 1
    g2[1] = 1

    
    inverse = [0] * (N + 1)
    inverse[0] = 0
    inverse[1] = 1

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

    return g1, g2, inverse


d = Counter(a).most_common(1)[0][0]
lr = [i for i, e in enumerate(a) if e == d]
l = lr[1] - lr[0] + 1
g1, g2, inverse = make_table(n)
MOD = 10 ** 9 + 7

answer = [(cmb(n, i) - cmb(n - l, i - 1)) % MOD for i in range(1, n + 1)]
print('\n'.join(map(str, answer)))

Solution (Python):
from collections import Counter

n, *a = map(int, open(0).read().split())
n += 1


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


mod = 10 ** 9 + 7
N = n

g1 = [0] * (N + 1)
g1[0] = 1
g1[1] = 1


g2 = [0] * (N + 1)
g2[0] = 1
g2[1] = 1


inverse = [0] * (N + 1)
inverse[0] = 0
inverse[1] = 1

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

d = Counter(a).most_common(1)[0][0]
lr = [i for i, e in enumerate(a) if e == d]
l = lr[1] - lr[0] + 1

answer = [(cmb(n, i, mod) - cmb(n - l, i - 1, mod)) % mod for i in range(1, n + 1)]
print('\n'.join(map(str, answer)))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def com(com_n, com_r):
    if com_n<com_r:return 0
    return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md



md = 10**9+7
n_max = 10**5+3
fac = [1]
inv = [1] * (n_max + 1)
k_fac_inv = 1
for i in range(1, n_max + 1):
    k_fac_inv = k_fac_inv * i % md
    fac.append(k_fac_inv)
k_fac_inv = pow(k_fac_inv, md - 2, md)
for i in range(n_max, 1, -1):
    inv[i] = k_fac_inv
    k_fac_inv = k_fac_inv * i % md

def main():
    n=int(input())
    aa=LI()
    pos=[-1]*(n+3)
    for i,a in enumerate(aa):
        if pos[a]==-1:pos[a]=i
        else:lr=n-i+pos[a]
    for k in range(1,n+2):
        ans=com(n+1,k)-com(lr,k-1)
        print(ans%md)

main()

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**5+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()) 
n += 1
a = list(map(int,input().split()))

x = y = 0
b = [-1 for i in range(n)]
for i in range(len(a)):
    if b[a[i]] != -1:
        x = b[a[i]]
        y = i
        break 
    else:
        b[a[i]] = i

for k in range(1,n+1):
    print((cmb(n,k,mod)-cmb(n+x-y-1,k-1,mod))%mod)

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

from collections import Counter
c = Counter(a)
for k in c.keys():
    if c[k] == 2:
        break
l = []
for i in range(len(a)):
    if a[i] == k:
        l.append(i)
    if len(l) == 2:
        break
d = n - l[1] + l[0]

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

mod = 10 ** 9 + 7
N = n + 2

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

inverseFactorial = [0] * N
inverseFactorial[N - 1] = power(factorial[N - 1], mod - 2)
for i in range(N - 2, -1, -1):
    inverseFactorial[i] = inverseFactorial[i + 1] * (i + 1) % mod

def comb(x, y):
    return factorial[x] * inverseFactorial[y] * inverseFactorial[x - y] % mod

for k in range(1, n + 2):
    if d >= k - 1:
        print((comb(n+1, k) - comb(d, k-1)) % mod)
    else:
        print(comb(n+1, k))

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

from collections import Counter
c = Counter(a)
for k in c.keys():
    if c[k] == 2:
        break
l = []
for i in range(len(a)):
    if a[i] == k:
        l.append(i)
    if len(l) == 2:
        break
d = n - l[1] + l[0]

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

mod = (10 ** 9 + 7)

N1 = n + 2
factorial1 = [1]
for i in range(1, N1):
    factorial1.append(factorial1[i - 1] * i % mod)
inverseFactorial1 = [0] * N1
inverseFactorial1[N1 - 1] = power(factorial1[N1 - 1], mod - 2)
for i in range(N1 - 2, -1, -1):
    inverseFactorial1[i] = inverseFactorial1[i + 1] * (i + 1) % mod
def combi1(x, y):
    return factorial1[x] * inverseFactorial1[y] * inverseFactorial1[x - y] % mod

for k in range(1, n + 2):
    if d >= k - 1:
        print((combi1(n+1, k) - combi1(d, k-1)) % mod)
    else:
        print(combi1(n+1, k))

Solution (Python):
def main():
    from collections import Counter as ct
    fact=[1]
    mod=10**9+7
    n=int(input())
    a=list(map(int,input().split()))
    for i in range(1,n+2):
        fact.append((fact[-1]*i)%mod)
    def inv_n(n,mod=10**9+7):return pow(n,mod-2,mod)
    def nCr(n,r,mod=10**9+7):return inv_n(fact[n-r]*fact[r]%mod,mod)*fact[n]%mod
    c=ct(a).most_common()[0][0]
    p,q=-1,-1
    for i in range(n+1):
        if a[i]==c:
            if p==-1:
                p=i
            else:
                q=i
    x=p+n-q
    for k in range(1,n+2):
        ans=0
        if k-2>=0:
            ans+=nCr(n-1,k-2)
        if k<=n-1:
            ans+=nCr(n-1,k)
        if k<=n:
            ans+=2*nCr(n-1,k-1)
        if k-1<=x:
            ans-=nCr(x,k-1)
        print((ans+mod)%mod)
main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class modfact(object):
    def __init__(self,n):
        fact=[1]*(n+1)
        invfact=[1]*(n+1)
        for i in range(1,n+1):
            fact[i]=i*fact[i-1]%MOD
        invfact[n]=pow(fact[n],MOD-2,MOD)
        for i in range(n-1,-1,-1):
            invfact[i]=invfact[i+1]*(i+1)%MOD
        self.__fact=fact
        self.__invfact=invfact

    def fact(self,n):
        return self.__fact[n]

    def invfact(self,n):
        return self.__invfact[n]

    def comb(self,n,k):
        if(k<0 or n-k<0): return 0
        return (self.fact(n)*self.invfact(k)*self.invfact(n-k))%MOD

from collections import Counter
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    C=Counter(A).most_common()
    a=C[0][0]
    for i in range(n+1):
        if(A[i]==a):
            A[i]=0
            l=i
            break
    for i in range(n+1):
        if(A[i]==a):
            A[i]=0
            r=i

    mf=modfact(n+1)
    for k in range(1,n+2):
        print((mf.comb(n+1,k)-mf.comb(l+n-r,k-1))%MOD)
resolve()

Solution (Python):
n = int(input())
A = [int(a) for a in input().split()]

pos = [-1]*n
for i in range(n+1):
    if pos[A[i]-1] >= 0:
        idx1 = pos[A[i]-1]
        idx2 = i
        break
    pos[A[i]-1] = i

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

mod = 10**9+7 
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 )


ans = [0]*(n+2)
for k in range(1, n+2):
    ans[k] = cmb(n+1, k, mod)
    

print(n)
for k in range(2, n+2):
    c = cmb(idx1+n-idx2, k-1, mod)
    print((ans[k]-c)%mod)

Solution (Python):
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


class Combinations:
    def __init__(self, max_num, mod):
        self.mod = mod
        self.factorials = [1]
        for i in range(1, max_num + 1):
            self.factorials.append((self.factorials[-1] * i) % mod)
        self.invs = [pow(self.factorials[-1], mod - 2, mod)]
        for i in reversed(range(1, max_num + 1)):
            self.invs.append(self.invs[-1] * i % mod)
        self.invs = self.invs[::-1]

    def __call__(self, n, k):
        if n < 0 or k < 0 or k > n:
            return 0
        return self.factorials[n] * self.invs[k] * self.invs[n - k] % self.mod


MOD = 10**9 + 7

n = ri()
ls = ril()
counter = collections.Counter(ls)
d = counter.most_common()[0][0]
l, r = [i for i in range(n + 1) if ls[i] == d]

combinations = Combinations(n + 1, MOD)
for k in range(1, n + 2):
    res = combinations(n + 1, k) - combinations(l + n - r, k - 1)
    res += MOD
    res %= MOD
    print(res)