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.



Sample input:
3
1 2 1 3


Sample output:
3
5
4
1

Submission status: Runtime Error

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

# MOD combination
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
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
    print((cmb(m,k)-cmb(m-2-ma,k-1))%mod)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
check = [[0,0]] * n
kasa = 0
kasa2 = 0
for i in range(n + 1):
  if check[a[i]][0] == 1:
    kasa = check[a[i]][1]
    kasa2 = i
    break
  check[a[i]][0] = 1
  check[a[i]][1] = i
kasa += 1
kasa2 += 1
def kaijo(num):
  val = 1
  for i in range(num):
    val *= i + 1
  return val
def conbination(num, num2):
  return kaijo(num) // (kaijo(num2) * kaijo(num - num2))
print(n)
for i in range(2, n+1):
  print((conbination(n+1, i) - conbination(kasa-1+n-kasa2, i-1)))
print(1)

Submission status: Runtime Error

Solution code:
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, 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)
    print(1)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
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, MOD)
    for i in range(1, n + 2):
        ans = com.get_cmb(n + 1, i) - com.get_cmb(l + n - r, i - 1)
        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline

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

MOD = 10 ** 9 + 7
SIZE = 2 * 10 ** 6

g1 = [1, 1]
g2 = [1, 1]
re = [1, 0]
for i in range(2, SIZE + 1):
    g1.append((g1[-1] * i) % MOD)
    re.append((-re[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * re[-1]) % MOD)

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

cnt = [0] * (N + 1)
for a in A:
    #print(a)
    cnt[a] += 1
#exit()
for a in range(N):
    if cnt[a] == 2:
        d_a = a
        break
for i in range(N - 1, -1, -1):
    if A[i] == d_a:
        r = i
        break
print(r)

def solve(r, k):
    if k == 1:
        return N
    else:
        print(N + 1, k)
        ret = comb(N + 1, k, MOD)
        print(ret)
        if k - 1 <= N - r:
            ret -= comb(N - r, k - 1, MOD)
        ret %= MOD
        return ret

for k in range(1, N + 1):
    print(solve(r, i))

Submission status: Runtime Error

Solution code:
from collections import Counter

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

Submission status: Runtime Error

Solution code:
import itertools
import collections
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

# 同じ数を特定する
same = collections.Counter(a)
for i, j in zip(same.values(), same):
    # print(i, j)
    if i == 2:
        same_number = j

# print(same_number)
c = [i for i, x in enumerate(a) if x == 19]
# print([i for i, x in enumerate(a) if x == 19])
# print(c[0],c[1],n)
com_num = n - c[1] + c[0]
# print(com_num)

# b = cmb(n, 5)
# print(b)
# same = collections.Counter(a)
# print(test)
for i in range(1, n+2):
    # test = set(list(itertools.combinations(a, i+1)))
    if i == 1:
        answer = cmb(n+1, 1) - 1
    else:
        if com_num >= i-1:
            answer = cmb(n+1, i) - cmb(com_num, i-1)
            # print(cmb(n+1, i) , cmb(com_num, i), i)
            # print('pass')
        else:
            answer = cmb(n+1, i)

    print(answer % mod)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline


########   modあり modは素数  ###############
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**4
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

#print(s,f)

for i in range(1,n+1):
    sousuu=cmb(n+1,i,mod)
    tyouhuku=cmb(s+n-f,i-1,mod)
    print(sousuu-tyouhuku)
print(1)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

n = int(input())
a = []
arr = input().split()
for i in range(n+1):
    a.append(int(arr[i]))

dup = i
for i in set(a):
    if a.count(i) > 1:
        dup = i

index = [i for i, x in enumerate(a) if x ==dup]
l = index[0]
r = index[1]

for i in range(n+1):
    k = i + 1
    x = int(comb(n+1,k))
    y = int(comb(l+n-r, k-1))
    print(x - y)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

Submission status: Runtime Error

Solution code:
print("reference: maspy")

# 基本的に重複がない
# n+1Ck − (n+1)-(r-l+1)Ck−1
 
MOD = 10 ** 9 + 7
U = 10 ** 5 + 1

# (a ^ n % MOD) を2部探索的に求められる。
def power_mod(a, n):
  if n == 0:
    return 1
  x = (power_mod(a, n // 2) ** 2) % MOD
  return x if n % 2 == 0 else (a * x) % MOD

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

# 逆元を求めている。
def make_fact(fact, fact_inv):
  for i in range(1, U + 1):
    fact[i] = (fact[i - 1] * i) % MOD
  fact_inv[U] = power_mod(fact[U], MOD - 2)
  for i in range(U, 0, -1):　# [U, 1]
    fact_inv[i - 1] = (fact_inv[i] * i) % MOD

def comb(n, k):
  if k < 0 or k > n:
    return 0
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x
 
fact = [1] * (U + 1)
fact_inv = [1] * (U + 1)
make_fact(fact, fact_inv)
 
# ここまではcombのtableを作っている。
  
# 重複の起きる場所の間隔だけが問題
n = int(input())
A = [int(x) for x in input().split()]
 
memo = dict()
for i, a in enumerate(A): # lenを使うならこちらを積極的に。
  if a in memo: # 離脱条件を先に。
    d = i - memo[a]
    break
  memo[a] = i # ある数字が何番目にいるか。

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

Submission status: Runtime Error

Solution code:
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 = 10**9+7 #出力の制限
N = 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()) 
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)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
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**4
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
N = n
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)

Submission status: Runtime Error

Solution code:
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

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

Submission status: Runtime Error

Solution code:
class combination2():
    def __init__(self, n, mo=10 ** 9 + 7):
        self.fac = [0] * (n + 1)
        self.inv = [1] * (n + 1)
        self.fac[0] = 1
        self.fact(n,mo)
        for i in range(2, n + 1):
            self.inv[n] *= i
            self.inv[n] %= mo
        self.inv[n] = pow(self.inv[n], mo - 2, mo)
        for i in range(1, n):
            self.inv[n - i] = self.inv[n - i + 1] * (n - i + 1) % mo
        return

    def fact(self, n, mo):
        if self.fac[n] != 0:
            return self.fac[n]
        self.fac[n] = n * self.fact(n - 1,mo) % mo
        return self.fac[n]

    def invf(self, n):
        return self.inv[n]

    def comb(self, x, y, mo):
        if y < 0 or y > x:
            return 0
        return self.fac[x] * self.inv[x - y] * self.inv[y] % mo

def examD(mod):
    N = I()
    a = LI()
    double = []
    for s in a:
        if s in double:
            cur = s
            break
        double.append(s)
    curL = a.index(cur); curR = a[curL+1:].index(cur) + (curL+1)
    L = curL; M = curR-curL-1;  R = N - curR
#    print(curL,curR)
#    print(L,M,R)
    C = combination2(N+1,mod)
    ans = []
    ans.append(N)
    for i in range(2,N+2):
        cur = C.comb(N+1,i,mod)
        if N-1-M-(i-1)>=0:
            cur -= C.comb(N-1-M,i-1,mod)
        if cur<0:
            cur += mod
        ans.append(cur)
    for v in ans:
        print(v)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD(mod)

Submission status: Runtime Error

Solution code:
mod=10**9+7
MAX=10**5

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
    
def cmb(n,r,MOD):
    return g1[n]*g2[r]*g2[n-r]%MOD

n=int(input())
a=list(map(int,input().split()))
data=[0]*(n+1)
for i in range(n+1):
    data[a[i]]+=1
for i in range(1,n+1):
    if data[i]==2:
        b=i
        break
l=[]
for i in range(n+1):
    if a[i]==b:
        l.append(i)
c=l[1]-l[0]+1
for k in range(1,n+3-c):
    ans=cmb(n+1,k,mod)-cmb(n+1-c,k-1,mod)
    print(ans%mod)
for k in range(n+3-c,n+2):
    ans=cmb(n+1,k,mod)
    print(ans)

Submission status: Runtime Error

Solution code:
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
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()))
data=[0]*(n+1)
for i in range(n+1):
    data[a[i]]+=1
for i in range(1,n+1):
    if data[i]==2:
        b=i
        break
l=[]
for i in range(n+1):
    if a[i]==b:
        l.append(i)
c=l[1]-l[0]+1
for k in range(1,n+3-c):
    ans=cmb(n+1,k,mod)-cmb(n+1-c,k-1,mod)
    print(ans%mod)
for k in range(n+3-c,n+2):
    ans=cmb(n+1,k,mod)
    print(ans)

Submission status: Runtime Error

Solution code:
#66d
#import itertools
import collections

from functools import lru_cache

import sys
sys.setrecursionlimit(100000)

mod_by = 7 + 10**9

@lru_cache(maxsize=None)
def get_num_of_permutations(n,k):
    if k==1:
        return n
    else:
        return get_num_of_permutations(n-1,k-1)*n
    
@lru_cache(maxsize=None)
def factorial(n):
    if n<=1:
        return 1
    else:
        return math.factorial(n)
    
@lru_cache(maxsize=None)
def get_num_of_combinations(n,k):
    return get_num_of_permutations(n,k)//factorial(k)

n = int(input())

a_list = [int(e) for e in input().split()]
index_list = [i for i in range(1,len(a_list)+1)]

a_dict = dict(zip(index_list,a_list)) #dictの入力順序付き

#重複している値のインデックスを求める
c = collections.Counter(a_list)
#print(c.most_common()[0][0])
keys = [k for k, v in a_dict.items() if v == c.most_common()[0][0]]

before_repeated = keys[0]-1
after_repeated = n+1-keys[1]

#print(keys,"→",keys[0]-1,n+1-keys[1])

for k in range(1,n+2,1):
    if k==1:
        print(n)
    elif k==n+1:
        print(1)
    else:
        all = get_num_of_combinations(n+1,k)%mod_by
        
        #愚直解
        #l = list(itertools.combinations(a_list, k))
        #repeated = [x for x in set(l) if l.count(x) > 1]
        #print(all-repeated)
        
        repeated = 0
        
        for i in range(k):
            if i!=0:
                before = get_num_of_combinations(before_repeated,i)%mod_by
            else:
                before = 1
                
            if k-1-i!=0:
                after = get_num_of_combinations(after_repeated,k-1-i)%mod_by
            else:
                after = 1
            
            repeated += before*after%mod_by
            
        if (all - repeated)%mod_by < 0:
            print((all - repeated)%mod_by + mod_by)
        else:
            print((all - repeated)%mod_by)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second
# print (left, right)

left_lst = [1] * (left + 1) 
for i in range(1, left + 1):
    left_lst[i] = (left_lst[i - 1] * (left + 1 - i)) // i
# print (left_lst)

right_lst = [1] * (right + 1)
for i in range(1, right + 1):
    right_lst[i] = (right_lst[i - 1] * (right + 1 - i)) // i
# print (right_lst)


def calc(i): #1を含めてトータルi個選ぶ
    if i == 1:
        return 1
    count = 0
    #左側からl個、右側からr個選ぶ
    start = max((i - 1) - right, 0) #左側から最低限選ばないといけない個数
    for l in range(start, i):
        count += left_lst[l] * right_lst[i - 1 - l]
    return count

N = n + 1
tmp = 1
for i in range(1, n + 2):
    tmp = (tmp * (N + 1 - i))//i
    if left + right < i - 1:
        print (tmp % MOD)
        continue
    print ((tmp - calc(i)) % MOD)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second
# print (left, right)

left_lst = [1] * (left + 1) 
for i in range(1, left + 1):
    left_lst[i] = (left_lst[i - 1] * (left + 1 - i)) // i
# print (left_lst)

right_lst = [1] * (right + 1)
for i in range(1, right + 1):
    right_lst[i] = (right_lst[i - 1] * (right + 1 - i)) // i
# print (right_lst)


def calc(i): #1を含めてトータルi個選ぶ
    if i == 1:
        return 1
    count = 0
    #左側からl個、右側からr個選ぶ
    start = max((i - 1) - right, 0) #左側から最低限選ばないといけない個数
    for l in range(start, left + 1):
        count += left_lst[l] * right_lst[i - 1 - l]
    return count



N = n + 1
tmp = 1
for i in range(1, n + 2):
    tmp = (tmp * (N + 1 - i))//i
    if left + right < i - 1:
        print (tmp % MOD)
        continue
    print ((tmp - calc(i)) % MOD)

Submission status: Runtime Error

Solution code:
INFTY = 10**9+7
memo = {}
def f(i,j):
    if j>i:
        return 0
    if j==0 or j==i:
        return 1
    if j==1 or j==i-1:
        return i
    if (i,j) in memo:
        return memo[(i,j)]
    memo[(i,j)] = (f(i-1,j-1)+f(i-1,j))%INFTY
    return memo[(i,j)]
n = int(input())
A = list(map(int,input().split()))
C = {i:0 for i in range(1,n+2)}
for i in range(n+1):
    C[A[i]] += 1
B = []
for i in range(n+1):
    if C[A[i]]==2:
        B.append(i)
m = B[1]-B[0]-1
for k in range(1,n+2):
    if k==1:
        print(n)
    elif k==n+1:
        print(1)
    else:
        print((f(n+1,k)-f(n-1-m,k-1))%INFTY)

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

const long long MOD = 1e9 + 7;

class Combination {
    //a^p%mod
    ll powmod(ll a, ll p) {
        ll ans = 1LL;
        ll mul = a;
        // p >>=1 <-> p=(p >> 1)
        for (; p > 0; p >>= 1, mul = (mul * mul) % mod) {
            if ((p & 1) == 1) ans = (ans * mul) % mod;
        }

        return ans;
    }
public:
    int N;
    ll mod;
    vector<ll> fact;
    vector<ll> revFact;

    Combination(int n, ll m) : N(n), mod(m), fact(n+1), revFact(n+1) {
        fact[0] = 1;
        for (int i = 1; i <= N; i++) {
            fact[i] = fact[i-1] * i;
            fact[i] %= mod;
        }

        // Fermat's little theorem
        revFact[N] = powmod(fact[N], mod - 2);

        for (int i = N-1; i >= 0; i--) {
            revFact[i] = revFact[i+1] * (i+1);
            revFact[i] %= mod;
        }
    }

    ll get(int a, int b) {
        if (a < 0 || b < 0) return 0;
        if (b > a) return 0;
        return (((fact[a] * revFact[b]) % mod) * revFact[a-b]) % mod;
    }
};

int main(){
  int N;
  cin >> N;
  int a[N + 1];
  for(int i = 0; i < N + 1; i++) cin >> a[i];

  int cnt[N];
  fill(cnt, cnt + N, 0);
  for(int i = 0; i < N + 1; i++) cnt[a[i] - 1]++;

  int num;
  for(int i = 0; i < N; i++){
    if(cnt[i] == 2){
      num = i + 1;
      break;
    }
  }

  vector<int> pos;
  for(int i = 0; i < N + 1; i++){
    if(a[i] == num) pos.push_back(i);
  }

  int c = pos[0] + (N - pos[1]);

  Combination cm = Combination(N + 5, MOD);

  for(int k = 1; k <= N + 1; k++){
    ll ans = cm.get(N + 1, k);
    ans -= cm.get(c, k - 1);
    ans %= MOD;

    cout << ans << endl;
  }

  return 0;
}

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))
search = [-1 for i in range(n)]
l,r = -1,-1
for i,x in enumerate(a):
    if search[x-1] == -1:
        search[x-1] = i
    else:
        l = search[x-1]
        r = i
#print(l,r)
p = 10**9 + 7

#前計算
comb1 = [0 for _ in range(n+1)]
comb1[0] = n+1
x = n+1
for i in range(1,n+1):
    x = (x*(n-i+1))%p
    x = (x*pow(i+1,p-2,p))%p
    comb1[i] = x

comb2 = [0 for _ in range(n+1)]
comb2[0] = 1
x = 1
for i in range(1,l+n-r+1):
    x = (x*(n+l-r-i+1))%p
    x = (x*pow(i,p-2,p))%p
    comb2[i] = x

for i in range(n+1):
    ans = comb1[i]-comb2[i]

    print(ans%p)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n]*pow(fact[r],mod-2,mod)*pow(fact[n-r],mod-2,mod) % mod
n = I()
a = LI()
f = defaultdict(lambda : 0)
for i in range(n):
    if f[a[i]] == 0:
        f[a[i]] += 1
    else:
        x = a[i]
        break
fact = [0]*(n+2)
fact[0] = 1
for i in range(1,n+2):
    fact[i] = i*fact[i-1]

lst = []
for i in range(n+1):
    if a[i] == x:
        lst.append(i+1)
a,b = lst[0],lst[1]
for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)

Submission status: Runtime Error

Solution code:

n = int(input())

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

indlis = [-1] * (n+1)


for i in range(n):

    if indlis[a[i]] == -1:
        indlis[a[i]] = i

    else:
        L = indlis[a[i]]
        R = i
        break

#print (L,R)
nall = n+1
nsub = 1

for i in range(n+1):

    print ((nall - nsub) % (10 ** 9 + 7))

    nall *= n - i
    nall //= 2+i

    nsub *= n-R+L-i
    nsub //= 1+i

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <limits.h>
#include <queue>
#include <map>
#include <ctime>
#include <set>

using namespace std;

#define rip(i,n,s) for (int i=(s);i<(int)(n);i++)
#define all(a) (a).begin(),(a).end()
typedef long long ll;

long long pow(long long n, long long p, long long k) {//n^k(mod p)
	if (k != 0) {
		if (k % 2 == 0) {
			long long x = pow(n, p, k / 2);
			return (long long)x*x%p;
		}
		else {
			long long x = pow(n, p, k - 1);
			return (long long)x*n%p;
		}
	}
	return 1;
}

long long rev(long long n, long long p) {//nの逆元
	return pow(n, p, p - 2);
}

long long bino(long long n, long long m, long long p) {//nCm(mod p)
	long long me = 1;
	long long ans = 1;
	for (int i = 0;i < n + m;i++) {
		me = (long long)(i + 1) * ans % p;
		if (i == m - 1) {
			ans = (long long)rev(me, p) * ans%p;
		}
		if (i == m - n - 1) {
			ans = (long long)(rev(me, p))*ans%p;
		}
	}
	ans = (long long)(ans*me%p);
	return ans;
}

struct modint {
	long long num;
	long long p;
	modint() {
		num = 0;
		p = 1000000007;
	}
	modint(int x) {
		num = (long long)x%p;
		p = 1000000007;
	}
	modint operator+(const modint &other) {
		modint ret;
		ret.p = p;
		ret.num = (num + other.num) % p;
		return ret;
	}
	modint operator+(const long long &other) {
		modint ret;
		ret.p = p;
		ret.num = (num + (other%p)) % p;
		return ret;
	}
	modint operator-(const modint &other) {
		modint ret;
		ret.p = p;
		ret.num = (num - other.num + p) % p;
		return ret;
	}
	modint operator-(const long long &other) {
		modint ret;
		ret.p = p;
		ret.num = (num - (other%p) + p) % p;
		return ret;
	}
	modint operator*(const modint &other) {
		modint ret;
		ret.p = p;
		ret.num = (num*other.num) % p;
		return ret;
	}
	modint operator*(const long long &other) {
		modint ret;
		ret.p = p;
		ret.num = (num*(other%p)) % p;
		return ret;
	}
	modint operator/(const modint &other) {
		modint ret;
		ret.p = p;
		ret.num = (num*rev(other.num, p)) % p;
		return ret;
	}
	modint operator/(const long long &other) {
		modint ret;
		ret.p = p;
		ret.num = (num*rev(other%p, p)) % p;
		return ret;
	}
};

int main() {
	int n, fo, ba;
	cin >> n;
	vector<int> ju(n, -1);
	vector<modint> da(n + 1);
	rip(i, n + 1, 0) {
		cin >> da[i].num;
		if (ju[da[i].num - 1] > -1) {
			fo = ju[da[i].num - 1];
			ba = i;
		}
		else {
			ju[da[i].num - 1] = i;
		}
	}
	vector<modint> ans(n + 1);
	modint no(1);
	rip(i, n + 1, 0) { //not x and both x
		no = no * ((long long)n + 1 - i) / ((long long)i + 1);
		ans[i] = ans[i] + no;
	}
	int di = n - (ba - fo);
	no = modint(1);
	ans[0] = ans[0] - 1;
	rip(i, di, 0) {
		no = no * ((long long)di - i) / ((long long)i + 1);
		ans[i + 1] = ans[i + 1] - no ;
	}
	rip(i, n + 1, 0) {
		printf("%lld\n", ans[i].num);
	}
}

Submission status: Runtime Error

Solution code:
from statistics import mode
n=int(input())
a=list(map(int,input().split()))
t=mode(a)
b=[i for i in range(n)if a[i]==t]
c=n+1
d=1
m=10**9+7
for i in range(1,n+2):
    if i==1:
        print(n)
    else:
        c=(c*(n-i+2))//i
        d=(d*(n-b[1]+b[0]+2-i))//(i-1)
        print((c-d)%m)