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:
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)
        print(ret)
        # for j in range(k + 1):
        #     ret -= cmb(li, j) * cmb(n - ri, k - j - 1)
        # PxQxRのPRからk-1個とる
        # PRの取り方の総和を求めるより、区間PRに含まれる総個数からk-1個選ぶ方法を考える


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


n=int(input())
A=list(map(int,input().split()))
v=[-1]*n
for i,a in enumerate(A):
    #print(i,a)
    if v[a-1]!=-1:
        s=v[a-1]
        f=i
    if v[a-1]==-1:
        v[a-1]=i

#print(s,f)
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%=mod
        sousuu//=i
        tyouhuku*=(s+n-f+1-i+1)
        tyouhuku%=mod
        tyouhuku//=(i-1)
    #print(sousuu,tyouhuku)
    print((sousuu-tyouhuku)%mod)
print(1)

Submission status: Wrong Answer

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


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result%mod
n=int(input())
A=list(map(int,input().split()))
v=[-1]*n
for i,a in enumerate(A):
    #print(i,a)
    if v[a-1]!=-1:
        s=v[a-1]
        f=i
    if v[a-1]==-1:
        v[a-1]=i

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

Submission status: Wrong Answer

Solution code:
from scipy.misc 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: Wrong Answer

Solution code:
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
cho=Counter(a).most_common()[0][0] #重複してる数字。

temp=[]
for i,j in enumerate(a):
  if j==cho:
    temp.append(i)

#1つ目の重複数の位置
x=temp[0]

#2つ目の重複数の位置
y=temp[1]

from operator import mul
from functools import reduce

def cmb(n,r):
    if n<r: return 0
    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

for i in range(1,n+2): #長さiの部分列
  #選び方全部は何通り？
  zenbu=cmb(n+1, i)

  #そこから、重複を引く。
  temp=0

  #左と右の配分の合計はi-1。
  for j in range(i):
    temp+=cmb(x,j)*cmb((n+1)-y-1, i-1-j)
    #print(i,j,cmb(x,j),cmb((n+1)-y-1, i-1-j))
  print(zenbu-temp)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
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

    # 1つ目のtwiceValueより左にある数字の数  
    left = first_index

    # 2つ目のtwiceValueより右にある数字の数  
    right = n-second_index
    edge = left+right

    # nCk,edgeCkをO(1)で取れるようにするため
    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

    # nCkをうめる
    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
    # edgeCkをうめる
    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)
    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))  # type: int
    a = [int(next(tokens)) for _ in range(n + 1)]  # type: "List[int]"
    solve(n, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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] % self.mod
        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
    print(ans)

Submission status: Wrong Answer

Solution code:
# 解説を見た

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)
        print(res)


if __name__ == '__main__':
    main()

# PxQxR
# PxRが重複

# 重複要素xの含まれる個数で場合分けをする

# xを含まない
# xを2個とも含む
# 一意

# xを1個含む場合でも、
# Qの要素を含む場合は、どっちのxを取ったか分かる

# Qの要素を含まないとき、どっちのxを取ったか分からない
# cmb(N+1,K)-cmb(PRの総和,K-1)

Submission status: Wrong Answer

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

    def prepare_factorial(self, N):
        self.f = [1]*(N+1) # f[n] := n!
        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 # a^(p-1) = 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)

Submission status: Wrong Answer

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

    def prepare_factorial(self, N):
        self.f = [1]*(N+1) # f[n] := n!
        p = 1
        for i in range(1,N+1):
            p = (p*i) % self.mod
            self.f[i] = p

    def modpow(self, x, k):
        x %= self.mod
        k %= self.mod-1 # a^(p-1) = 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.modpow(self.f[n-k], -1) * self.modpow(self.f[k], -1) % 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)

Submission status: Wrong Answer

Solution code:
class ModWorld:
    def __init__(self, mod):
        self.mod = mod
        self.memo_inv = {}

    def prepare_factorial(self, N):
        self.f = [1]*(N+1) # f[n] := n!
        p = 1
        for i in range(1,N+1):
            p = (p*i) % self.mod
            self.f[i] = p

    def modpow(self, x, k):
        if k==-1 and x in self.memo_inv: return self.memo_inv[x]
        
        x %= self.mod
        k %= self.mod-1 # a^(p-1) = 1
        retval = 1
        while k:
            if k&1: retval *= x
            k>>=1
            x = x*x % self.mod

        if k==-1%(self.mod-1): self.memo_inv[x] = retval % self.mod 
        return retval % self.mod

    def modcomb(self, n, k):
        return self.f[n] * self.modpow(self.f[n-k], -1) * self.modpow(self.f[k], -1) % 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(k, mw.modcomb(n+1, k), mw.modcomb(n+1-m, k-1), ans)
    print(ans)

Submission status: Wrong Answer

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

    def prepare_factorial(self, N):
        self.f = [1]*(N+1) # f[n] := n!
        p = 1
        for i in range(1,N+1):
            p = (p*i) % self.mod
            self.f[i] = p

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

    def modcomb(self, n, k):
        return self.f[n] * self.modpow(self.f[n-k], -1) * self.modpow(self.f[k], -1) % 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 = abs(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)

Submission status: Wrong Answer

Solution code:
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) for i in range(1, n + 1)]
print('\n'.join(map(str, answer)))

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

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

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)

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):
    if x < y:
        return 0
    else:
        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))
    else:
        print(combi1(n+1, k))

Submission status: Wrong Answer

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)

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

N2 = d + 1
factorial2 = [1]
for i in range(1, N2):
    factorial2.append(factorial2[i - 1] * i % mod)
inverseFactorial2 = [0] * N2
inverseFactorial2[N2 - 1] = power(factorial2[N2 - 1], mod - 2)
for i in range(N2 - 2, -1, -1):
    inverseFactorial2[i] = inverseFactorial2[i + 1] * (i + 1) % mod
def combi2(x, y):
    return factorial2[x] * inverseFactorial2[y] * inverseFactorial2[x - y] % mod



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

Submission status: Wrong Answer

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)
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 combi(x, y):
    return factorial[x] * inverseFactorial[y] * inverseFactorial[x - y] % mod


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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n = I() + 1
A = LI()


fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


D = defaultdict(lambda:-1)
for i in range(n + 1):
    if D[A[i]] != -1:
        l = D[A[i]]
        r = n - i - 1
        break
    else:
        D[A[i]] = i

for k in range(1, n + 1):
    print(comb(n, k) - comb(l + r, k - 1) % mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n = I() + 1
A = LI()


fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


D = defaultdict(lambda:-1)
for i in range(n):
    if D[A[i]] != -1:
        l = D[A[i]]
        r = n - i - 1
        break
    else:
        D[A[i]] = i

for k in range(1, n + 1):
    print(comb(n, k) - comb(l + r, k - 1) % mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n = I() + 1
A = LI()


fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


D = defaultdict(lambda:-1)
for i in range(n):
    if D[A[i]] != -1:
        l = D[A[i]]
        r = i
    else:
        D[A[i]] = i

for k in range(1, n + 1):
    print(comb(n, k) - comb(l + (n - r - 1), k - 1) % mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n = I() + 1
A = LI()


fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


D = defaultdict(lambda:-1)
for i in range(n):
    if D[A[i]] != -1:
        l = D[A[i]]
        r = i
    else:
        D[A[i]] = i

for k in range(1, n + 1):
    print(comb(n, k) - comb(l + (n - r - 1), k - 1))

Submission status: Wrong Answer

Solution code:
class combination():
    #素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

        self.inv[n] = pow(self.fac[n], mod - 2, mod)
        for j in range(n - 1, -1, -1):
            self.inv[j] = self.inv[j + 1] * (j + 1) % mod

    def comb(self, n, r, mod):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % mod

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 = combination(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)
        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: Wrong Answer

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

mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
a.sort()
for i in range(1,n+1):
    if a[i]==a[i-1]:
        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)
    print(ans%mod)
for k in range(n+3-c,n+2):
    ans=cmb(n+1,k)%mod
    print(ans)