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: Wrong Answer

Solution code:
mod = 10**9+7
MAX = 10**5+1
fact = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i)%mod
inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[mod%i]*(mod-mod//i)%mod
fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1]*inv[i]%mod
def comb(n, r):
    if n < r:
        return 0
    return fact[n]*fact_inv[n-r]*fact_inv[r] % mod

n = int(input())
L = list(map(int,input().split()))
M = []
for i in range(n+1):
    M.append(L[i])
M.sort()
dou = 1 #重複する数
for i in range(n+1):
    if M[i] == dou:
        dou += 1
    else:
        dou = M[i]
        break
l = 0
r = 0
cnt = 0
for i in range(n+1):
    if L[i] == dou and cnt == 0:
        l = i+1
        cnt += 1
    elif L[i] == dou and cnt == 1:
        r = i+1
        break
for i in range(1,n+1):
    print(comb(n+1,i)-comb(l+n-r,i-1))
print(1)

Submission status: Wrong Answer

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

dup=[0]*n
for num in a:
    dup[num-1]+=1
    if dup[num-1]>1:
        break

A=-1
B=-1
for i in range(len(a)):
    if a[i]==num:
        if A==-1:
            A=i
        else:
            B=i
B=n-B

def find_power(n,mod=10**9+7):
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
def find_inv_power(n,mod=10**9+7):
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

mod = 10**9+7
NUM = (10**5)+100
p_lis=find_power(NUM,mod)
ip_lis=find_inv_power(NUM,mod)

def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (p_lis[n]*ip_lis[r]*ip_lis[n-r])%(mod)

print(n)
for k in range(2,n+2):
    base=comb(n+1,k)
    base-= comb(A+B,k-1)

    print(base)

Submission status: Wrong Answer

Solution code:
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
c=[0]*n
for i in a:c[i-1]+=1
ind=c.index(2)
x=[]
for i in range(n+1):
    if a[i]==ind+1:x.append(i)
m=n+x[0]-x[1]
f=[1]
for i in range(1,n+2):f.append(f[-1]*i%mod)
def comb(n,r):return f[n]*pow(f[r],mod-2,mod)*pow(f[n-r],mod-2,mod)%mod
for k in range(1,n+2):
    if k==1:print(n);continue
    if k>=m:print(comb(n+1,k));continue
    ans=comb(n+1,k)-comb(m,k-1)
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
c=[0]*n
for i in a:c[i-1]+=1
ind=c.index(2)
x=[]
for i in range(n+1):
    if a[i]==ind+1:x.append(i)
l=x[0]
r=n-x[1]
f=[1]
for i in range(1,n+2):f.append(f[-1]*i%mod)
def comb(n,r):return f[n]*pow(f[r],mod-2,mod)*pow(f[n-r],mod-2,mod)%mod
lc=[comb(l,i)for i in range(l+1)]
lc[0]=0
for i in range(1,l+1):lc[i]+=lc[i-1]
rc=[comb(r,i)for i in range(r+1)]
rc[0]=0
for i in range(1,r+1):rc[i]+=rc[i-1]
for k in range(1,n+2):
    if k==1:print(n);continue
    ans=comb(n+1,k)
    if k-1<=l:ans-=lc[min(l,k-1)]-(lc[k-((n+1)-l)] if (n+1)-l<k else 0)
    if k-1<=r:ans-=rc[min(r,k-1)]-(rc[k-((n+1)-r)] if (n+1)-r<k else 0)
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
c=[0]*n
for i in a:c[i-1]+=1
ind=c.index(2)
x=[]
for i in range(n+1):
    if a[i]==ind+1:x.append(i)
l=x[0]
r=n-x[1]
f=[1]
for i in range(1,n+2):f.append(f[-1]*i%mod)
def comb(n,r):return f[n]*pow(f[r],mod-2,mod)*pow(f[n-r],mod-2,mod)%mod
lc=[comb(l,i)for i in range(l+1)]
lc[0]=0
for i in range(1,l+1):lc[i]+=lc[i-1]
rc=[comb(r,i)for i in range(r+1)]
rc[0]=0
for i in range(1,r+1):rc[i]+=rc[i-1]
for k in range(1,n+2):
    if k==1:print(n);continue
    ans=comb(n+1,k)
    if k-1<=l:ans-=lc[min(l,k-1)]-(lc[k-((n+1)-l)] if (n+1)-l<k else 0)
    if k-1<=r:ans-=rc[min(r,k-1)]-(rc[k-((n+1)-r)] if (n+1)-r<k else 0)
    print(ans)

Submission status: Wrong Answer

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

d = {}
for i in range(n+1):
    if A[i] not in d:
        d[A[i]] = i
    else:
        l = d[A[i]]
        r = i
        break
#print(l, r)

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

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

N = int(input())
A = list(map(int, input().split()))
comb = Combination(N + 100)

cntA = Counter(A)
I = [a for a, c in cntA.items() if c == 2][0]
L, R = [i for i, a in enumerate(A) if a == I]
S = L + (N - R)

for i in range(1, N + 2):
    if i == 1:
        print(N)
        continue

    ans = comb.ncr(N + 1, i) - comb.ncr(S, i - 1)
    print(ans)

Submission status: Wrong Answer

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

from collections import Counter
ctr = Counter(A)
d = ctr.most_common(1)[0][0]
x = A.index(d)
y = x+1 + A[x+1:].index(d)
f = x + N-y

MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+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 comb(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 i in range(1,N+2):
    ans.append(comb(N+1,i) - comb(f,i-1))
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import Counter


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

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

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


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    comb = Combination(N + 10)
    X = Counter(A).most_common()[0][0]

    l = A.index(X)
    r = A.index(X, l+1)
    LR = l + (N - r)

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

Submission status: Wrong Answer

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
    ans=0
    ans+=cmb(m-2,k)
    ans+=cmb(m-2,k-2)
    if m-ma-2>=k-1:
        ans+=cmb(m-ma-2,k-1)
    for i in range(max(1,m-ma-k-2),ma+1):
        if k-1-i>=0:
            ans+=2*cmb(ma,i)*cmb(m-ma-2,k-1-i)
        else:
            break
    print(ans%mod)

Submission status: Wrong Answer

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

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ct=[0]*n
X=[]
for i in range(n+1):
  ct[a[i]-1]+=1
for i in range(n):
  if ct[i]==2:
    x=i+1
    break
for i in range(n+1):
  if a[i]==x:
    X.append(i)

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

for i in range(1,n+2):
    print(cmb(n+1,i,mod)-cmb(X[0]+n-X[1],i-1,mod))

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline

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

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

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

counter = Counter(a)
front = back = 0
for i in range(1, n+1):
    if counter[i] == 2:
        first = a.index(i)
        second = a[first+1:].index(i)
        front = first
        back = n - second - 1
        break

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

Submission status: Wrong Answer

Solution code:
def comb(n, r, p):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
        x %= p
        y %= p
    return pow(y, p - 2, p) * x % p

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
b = [-1] * (n + 1)
for i in range(n + 1):
    if b[a[i]] == -1:
        b[a[i]] = i
    else:
        s, t = b[a[i]], i
        break
c1 = s
c2 = n - t
c3 = n - 1
dp = [-1] * n
print(n)
for i in range(2, n + 1):
    ans = 0
    if dp[min(i - 2, c3 - i + 2)] == -1:
        dp[min(i - 2, c3 - i + 2)] = comb(c3, min(i - 2, c3 - i + 2), mod)
    ans += dp[min(i - 2, c3 - i + 2)]
    if dp[min(i - 1, c3 - i + 1)] == -1:
        dp[min(i - 1, c3 - i + 1)] = comb(c3, min(i - 1, c3 - i + 1), mod)
    ans += 2 * dp[min(i - 1, c3 - i + 1)]
    if not i == n:
        if dp[min(i, c3 - i)] == -1:
            dp[min(i, c3 - i)] = comb(c3, min(i, c3 - i), mod)
        ans += dp[min(i, c3 - i)]
    if c1 >= i - 1:
        ans -= comb(c1, min(i - 1, c1 - i + 1), mod)
    if c2 >= i - 1:
        ans -= comb(c2, min(i - 1, c2 - i + 1), mod)
    ans %= mod
    print(ans)
print(1)

Submission status: Wrong Answer

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


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline


#N=int(input())

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


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

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



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

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


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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

fac = [-1] * (10**6+1)
inv = [-1] * (10**6+1)
finv = [-1] * (10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        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 NCMMod(n, k):
    if n < k:
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

initNCMMod(100000)

def main():
    n = I()
    a = LI()
    tmp_set = set()
    e = -1
    i1, i2 = -1, -1
    for i in range(n+1):
        if a[i] in tmp_set:
            i2 = i
            e = a[i]
        tmp_set.add(a[i])
    for i in range(n+1):
        if a[i] == e:
            i1 = i
            break
    left = i1
    right = n - i2
    for k in range(1, n+2):
        if k == 1:
            print(n)
            continue

        cnt = NCMMod(n+1, k)
        cnt -= NCMMod(left+right, k-1)
        cnt %= mod
        print(cnt)
main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

fac = [-1] * (10**6+1)
inv = [-1] * (10**6+1)
finv = [-1] * (10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        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 NCMMod(n, k):
    if n < k:
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

initNCMMod(100000)

def main():
    n = I()
    a = LI()
    tmp_set = set()
    e = -1
    i1, i2 = -1, -1
    for i in range(n+1):
        if a[i] in tmp_set:
            i2 = i
            e = a[i]
        tmp_set.add(a[i])
    for i in range(n+1):
        if a[i] == e:
            i1 = i
            break
    left = i1
    middle = i2 - i1 - 1
    right = n + 1 - i2 - 1
    for k in range(1, n+2):
        if k == 1:
            print(n)
            continue

        cnt = NCMMod(n+1, k)
        r_rem = (n+1 - 1 - k) - middle
        if r_rem >= 0:
            l_rem = r_rem - right
            if r_rem == 0 and right == 0:
                pass
            else:
                if l_rem >= 0:
                    cnt -= NCMMod(left, l_rem)
                else:
                    cnt -= NCMMod(right, r_rem)
        
        l_lem = (n+1 - 1 - k) - middle
        if l_lem >= 0:
            r_rem = l_lem - left
            if l_lem == 0 and left == 0:
                pass
            else:
                if r_rem >= 0:
                    cnt -= NCMMod(right, r_rem)
                else:
                    cnt -= NCMMod(left, l_rem)
        print(cnt)
main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

fac = [-1] * (10**6+1)
inv = [-1] * (10**6+1)
finv = [-1] * (10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        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 NCMMod(n, k):
    if n < k:
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

initNCMMod(100000)

def main():
    n = I()
    a = LI()
    tmp_set = set()
    e = -1
    i1, i2 = -1, -1
    for i in range(n+1):
        if a[i] in tmp_set:
            i2 = i
            e = a[i]
        tmp_set.add(a[i])
    for i in range(n+1):
        if a[i] == e:
            i1 = i
            break
    left = i1
    middle = i2 - i1 - 1
    right = n + 1 - i2 - 1
    # import pdb
    # pdb.set_trace()
    for k in range(1, n+2):
        if k == 1:
            print(n)
            continue

        cnt = NCMMod(n+1, k)
        r_rem = (n+1 - 1 - k) - middle
        if r_rem >= 0:
            l_rem = r_rem - right
            if l_rem >= 0:
                cnt -= NCMMod(left, l_rem)
            else:
                cnt -= NCMMod(right, r_rem)
        
        l_lem = (n+1 - 1 - k) - middle
        if l_lem >= 0:
            r_rem = l_lem - left
            if r_rem >= 0:
                cnt -= NCMMod(right, r_rem)
            else:
                cnt -= NCMMod(left, l_rem)
        print(cnt)
main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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

MOD = 10 ** 9 + 7

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

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

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 5 + 10 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

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

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

if N > 1:
    print(1)
# 10

Submission status: Wrong Answer

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

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

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

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

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

fact = Factorial(n+1)

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

Submission status: Wrong Answer

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

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

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

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

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

fact = Factorial(n+1)

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

Submission status: Wrong Answer

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

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

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

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

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

fact = Factorial(n+1)

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

Submission status: Wrong Answer

Solution code:
# D - 11

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

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

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

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


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

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

Submission status: Wrong Answer

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

# print(kaburi)
# print(idx1, idx2)
l = idx1-1
r = n-idx2+1
idx1 -= 1
idx2 -= 1

thre = n-(idx2-idx1)+2
# print(l, r)

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

Submission status: Wrong Answer

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

# print(kaburi)
# print(idx1, idx2)
l = idx1-1
r = n-idx2+1
idx1 -= 1
idx2 -= 1

thre = n-(idx2-idx1)+2
print(l, r)

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