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:
import sys
from collections import Counter

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


factorials = get_factorials(N + 1, MOD)


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    def inv(a):
        """
        a の逆元
        :param a:
        :return:
        """
        return pow(a, mod - 2, mod)

    if mod:
        return factorials[n] * inv(factorials[r]) * inv(factorials[n - r]) % mod
    else:
        return factorials[n] // factorials[r] // factorials[n - r]


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

# dup より端から i 個選ぶ組み合わせ
sides = np.array([ncr(L + N - r, i, MOD) for i in range(N + 2)])

# 全部選んで選びすぎを引く
# dup を 1 つ選び、その他を dup より端から選ぶ組み合わせが重複する
ans = [ncr(N + 1, k, MOD) - sides[k - 1] for k in range(1, N + 2)]

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
from functools import lru_cache

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


factorials = get_factorials(N + 1, MOD)


@lru_cache(maxsize=None)
def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    def inv(a):
        """
        a の逆元
        :param a:
        :return:
        """
        return pow(a, mod - 2, mod)

    if mod:
        return factorials[n] * inv(factorials[r]) * inv(factorials[n - r]) % mod
    else:
        return factorials[n] // factorials[r] // factorials[n - r]


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

# L より左から i 個選ぶ組み合わせ
Lcr = np.array([ncr(L, i, MOD) for i in range(N + 2)])
# N-r より右から i 個選ぶ組み合わせ
Rcr = np.array([ncr(N - r, i, MOD) for i in range(N + 2)])[::-1]

for k in range(1, N + 2):
    c = ncr(N + 1, k, MOD)
    # 選びすぎを引く
    c -= np.dot(Lcr[:k], Rcr[-k:])
    # for i in range(k):
    #     c -= ncr(L, i, MOD) * ncr(N - r, k - i - 1, MOD)
    print(c % MOD)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
from functools import lru_cache

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


factorials = get_factorials(N + 1, MOD)


@lru_cache(maxsize=None)
def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    def inv(a):
        """
        a の逆元
        :param a:
        :return:
        """
        return pow(a, mod - 2, mod)

    if mod:
        return factorials[n] * inv(factorials[r]) * inv(factorials[n - r]) % mod
    else:
        return factorials[n] // factorials[r] // factorials[n - r]


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

for k in range(1, N + 2):
    c = ncr(N + 1, k, MOD)
    # 選びすぎを引く
    for i in range(k):
        d = ncr(L, i, MOD) * ncr(N - r, k - i - 1, MOD)
        if d == 0:
            break
        c -= d
    print(c % MOD)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
N = int(input())
A = [int(x) for x in input().split()]
se = []
c = sum(A) - N * (N + 1) / 2
for i in range(len(A)):
    if A[i] == c:
        se.append(i)
l = se[0]
r = se[1]
import math

print(N)

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


def nCr(n, r):
    if n < r or n == 0 or r == 0:
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % mod



for i in range(2,N+2):
    k = nCr(N+1, i)
    
    t = nCr(l+N-r,i-1)
    res  = k -t
    print(res)

Submission status: Wrong Answer

Solution code:
class BigCombination(object):
    __slots__ = ["mod", "factorial", "inverse"]

    def __init__(self, mod: int = 10**9+7, max_n: int = 10**6):
        fac, inv = [1], []
        fac_append, inv_append = fac.append, inv.append

        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

    def get_combination(self, n, r):
        if n < r or n == 0 or r == 0:
            return 0
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

    def get_permutation(self, n, r):
        return self.factorial[n] * self.inverse[n-r] % self.mod

N = int(input())
A = [int(x) for x in input().split()]
se = []
c = sum(A) - N * (N + 1) / 2
for i in range(len(A)):
    if A[i] == c:
        se.append(i)
l = se[0]
r = se[1]
import math

print(N)
Big = BigCombination()

for i in range(2,N+2):
    k = Big.get_combination(N+1, i)
    
    t = Big.get_combination(l+N-r,i-1)
    res  = k -t
    print(res)

Submission status: Wrong Answer

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

mod = 10**9+7

class combinationmod():
  def __init__(self,MAX, mod):
    self.mod =mod
    self.fac=[0]*(MAX+1)
    self.finv=[0]*(MAX+1)
    self.inv=[0]*(MAX+1)
    self.fac[0]=self.fac[1]=1
    self.finv[0]=self.finv[1]=1
    self.inv[1]=1
    for i in range(2,MAX+1):
      self.fac[i] = self.fac[i-1]*i%mod
      self.inv[i] = (-self.inv[mod%i]*(mod//i))%mod
      self.finv[i] = self.finv[i-1]* self.inv[i] %mod

  def nCk(self,n,k):
    if n<k or n<0 or k<0:
      return 0
    return self.fac[n]*(self.finv[k]*self.finv[n-k]%self.mod)%self.mod
  
memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
c = combinationmod(n+1,mod)
for k in range(1,n+2):
  print(c.nCk(n+1,k) - c.nCk(L+R,k-1))

Submission status: Wrong Answer

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

mod = int(1e9+7)

class combinationmod():
  def __init__(self,MAX, mod):
    self.mod =mod
    self.fac=[0]*(MAX+1)
    self.finv=[0]*(MAX+1)
    self.inv=[0]*(MAX+1)
    self.fac[0]=self.fac[1]=1
    self.finv[0]=self.finv[1]=1
    self.inv[1]=1
    for i in range(2,MAX+1):
      self.fac[i] = self.fac[i-1]*i%mod
      self.inv[i] = (-self.inv[mod%i]*(mod//i))%mod
      self.finv[i] = self.finv[i-1]* self.inv[i] %mod

  def nCk(self,n,k):
    if n<k or n<0 or k<0:
      return 0
    return self.fac[n]*(self.finv[k]*self.finv[n-k]%self.mod)%self.mod
  
memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
c = combinationmod(n,mod)
for k in range(1,n+2):
  print(c.nCk(n,k) - c.nCk(L+R,k-1))

Submission status: Wrong Answer

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

mod = int(1e9+7)

class combinationmod():
  def __init__(self,MAX, mod):
    self.mod =mod
    self.fac=[0]*(MAX+1)
    self.finv=[0]*(MAX+1)
    self.inv=[0]*(MAX+1)
    self.fac[0]=self.fac[1]=1
    self.finv[0]=self.finv[1]=1
    self.inv[1]=1
    for i in range(2,MAX+1):
      self.fac[i] = self.fac[i-1]*i%mod
      self.inv[i] = (-self.inv[mod%i]*(mod//i))%mod
      self.finv[i] = self.finv[i-1]* self.inv[i] %mod

  def nCk(self,n,k):
    if n<k or n<0 or k<0:
      return 0
    return self.fac[n]*(self.finv[k]*self.finv[n-k]%self.mod)%self.mod
  
memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
c = combinationmod(n+1,mod)
for k in range(1,n+2):
  print(c.nCk(n+1,k) - c.nCk(L+R,k-1))

Submission status: Wrong Answer

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

mod = int(1e9+7)
def powermod(a, n, mod):
    r = 1
    while n>1:
        if n%2:
            r = r*a%mod
        a = a*a%mod
        n = n//2
    return r

memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [0]*(n+3)
_LCR = [0] * (n+3) # _LCR[k] = (L+C+R)C(k)
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) #LR[k] = (L+R)C(k)
LR[0] = 1
#LDR = [0]*(n+2)
#LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
#LDCR = [0] * (n+2) #最後に*2を忘れないこと
#LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * powermod(k, mod-2, mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
#  LDR[k] = LR[k-1]
#  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]
#  LDCR[k] = LCR[k-1]
#  LDCDR[k] = LDCR[k-1]
  #print(LR, LCR)
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

Submission status: Wrong Answer

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

mod = int(1e9+7)

memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)

LR = [1]*(n+2) #LR[k] = (L+R)C(k)
LDR = [0]*(n+2)
LDDR = [0]*(n+2)

_LCR = [1] * (n+2) # _LCR[k] = (L+C+R)C(k)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
LDCR = [0] * (n+2) #最後に*2を忘れないこと
LDCDR = [0] * (n+2)

for k in range(1,n+2):
  LR[k] = (LR[k-1] * (L+R+1-k) // k)%mod
  LDR[k] = LR[k-1]
  LDDR[k] = LDR[k-1]
  
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k) // k)%mod
  
  LCR[k] = _LCR[k] - LR[k]
  LDCR[k] = LCR[k-1]
  LDCDR[k] = LDCR[k-1]
  
  print((LR[k] + LDR[k] + LDDR[k] + LCR[k] + 2*LDCR[k] + LDCDR[k])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math


n = int(input())
a = [int(i) for i in input().split()]

def combinations_count(n,r):
    if n-r < 0:
        return 0

    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))%(10**9+7)

A = copy.deepcopy(a)
A.sort()
for i in range(len(A)-1):
    if A[i] == A[i+1]:
        double = A[i]
        break

cnt = 0
for i in range(n+1):
    if a[i] == double:
        if cnt == 0:
            l = i+1
            cnt += 1
        else:
            r = i+1
print(l,r)
for k in range(1,n+2):
    # print(n+1,k,l-1+n-r,k-1)
    ans = combinations_count(n+1,k)-combinations_count((l+n-r),(k-1))
    print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math


n = int(input())
a = [int(i) for i in input().split()]

dp = [[0 for i in range(n+1)] for j in range(n+1)]

count = [0 for i in range(n+1)]


used = []
cnt =0
for i in range(n+1):
    if not a[i] in used:
        cnt += 1
        used.append(a[i])

    count[i] = cnt

dp[0] = count
for i in range(n+1):
    dp[i][i] = 1

for j in range(1,n+1):
    for i in range(1,j):
        dp[i][j] = (dp[i-1][j-1]+dp[i][j-1])%(10**9+7)


for i in range(n+1):
    print(dp[i][-1])

Submission status: Wrong Answer

Solution code:
from collections import*
n,*a=map(int,open(0).read().split())
b=len(a)
m=Counter(a).most_common()[0][0]
l,r=(k for k,v in enumerate(a) if v==m)
#print(l,r)
def mod_Combination(n, k, mod):
    def ext_gcd(a, b):
        if b == 0:return a, 1, 0
        else:d,x,y = ext_gcd(b,a%b);x-=(a//b)*y 
        return d,y,x
    p,q=1,1
    for i in range(n-k+1,n+1):
        p=(p*i)%mod
    for i in range(2,k+1):
        q=(q*i)%mod
    return int(p*(ext_gcd(q, mod)[1]%mod)%mod)

for i in range(b):
    print(mod_Combination(b,i+1,10**9+7)-mod_Combination(b-r-l+1,i,10**9+7))

Submission status: Wrong Answer

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

nCk = [0] * (n+2)
for i in range(1,n+2):
    if i == 1:
        nCk[1] = n+1
    else:
        nCk[i] = (nCk[i-1] * (n+1-i+1) // i) # % (10**9 + 7)

index = [-1] * (n+1)
l, r = 0, 0
for i, c in enumerate(a):
    if index[c] == -1:
        index[c] = i
    else:
        l = index[c]
        r = i

nb1Ck = [0] * (n + 2)
nb1Ck[1] = (n-r+l)
for i in range(1,(n-r+l)+2):
    if i == 1:
        nb1Ck[1] = n-r+l
    else:
        nb1Ck[i] = (nb1Ck[i-1] * ((n-r+l+1)-i) // i) # % (10**9 + 7)

for i in range(1, n+2):
    print((nCk[i] - nb1Ck[i-1])%(10**9 + 7))

Submission status: Wrong Answer

Solution code:
import sys
import string
from collections import Counter
mo=10**9+7
sys.setrecursionlimit(10000000)
alp=string.ascii_uppercase

def euc(x,y):
    x,y=max(x,y),min(x,y)
    if x%y==0:
        return y
    else:
        while(x%y!=0):
            x,y=y,x%y
        return y

n=int(input())
a=[int(i) for i in input().split()]
#print(len(a),a)
c=Counter(a)
db=c.most_common()[0][0]
#print(db)
fst=a.index(db)
lst=a.index(db,fst+1)
x=n+1-(lst-fst+1)
#print(fst,lst)

cn=[0]*(n+1+1)
cn[0]=1
cx=[0]*(x+1)
cx[0]=1
def com1(k):
    if k>n+1 or k<0:
        return 0
    if cn[k]!=0:
        return cn[k]
    cn[k]=((n+1-k+1)*cn[k-1])%mo//k
    return cn[k]
    
def com2(k):
    if k>x or k<0:
        return 0
    if cx[k]!=0:
        return cx[k]
    cx[k]=((x-k+1)*cx[k-1])%mo//k
    return cx[k]
    
for i in range(1,n+2):
    ans=com1(i)-com2(i-1)
    print(ans%mo)#,com1(i),com2(i-1))

Submission status: Wrong Answer

Solution code:
import sys
import string
from collections import Counter
mo=10**9+7
sys.setrecursionlimit(10000000)
alp=string.ascii_uppercase

def euc(x,y):
    x,y=max(x,y),min(x,y)
    if x%y==0:
        return y
    else:
        while(x%y!=0):
            x,y=y,x%y
        return y

n=int(input())
a=[int(i) for i in input().split()]
#print(len(a),a)
c=Counter(a)
db=c.most_common()[0][0]
#print(db)
fst=a.index(db)
lst=a.index(db,fst+1)
x=n+1-(lst-fst+1)
#print(fst,lst)

cn=[0]*(n+1+1)
cn[0]=1
cx=[0]*(x+1)
cx[0]=1
def com1(k):
    if k>n+1 or k<0:
        return 0
    if cn[k]!=0:
        return cn[k]
    cn[k]=((n+1-k+1)*cn[k-1]//k)%mo
    return cn[k]
    
def com2(k):
    if k>x or k<0:
        return 0
    if cx[k]!=0:
        return cx[k]
    cx[k]=((x-k+1)*cx[k-1]//k)%mo
    return cx[k]
    
for i in range(1,n+2):
    ans=com1(i)-com2(i-1)
    print(ans%mo)#,com1(i),com2(i-1))

Submission status: Wrong Answer

Solution code:
def _11(N: int, A: list)->list:
    MOD = 10**9 + 7

    d = {}
    l, r = 0, 0
    for i, a in enumerate(A):
        if a in d:
            l, r = d[a], N-i
        else:
            d[a] = i

    c1, c2 = [1]*(N+2), [1]*(N+2)
    for i in range(N+1):
        c1[i+1] = (c1[i] * (N+1-i) // (i+1)) % MOD
        c2[i+1] = (c2[i] * (l+r-i) // (i+1)) % MOD

    return [(c1[k+1]-c2[k]+MOD) % MOD for k in range(N+1)]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _11(N, A)
    print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
def _11(N: int, A: list)->list:
    MOD = 10**9 + 7

    d = {}
    l, r = 0, 0
    for i, a in enumerate(A):
        if a in d:
            l, r = d[a], N-i
        else:
            d[a] = i

    c1, c2 = N+1, 1
    ret = []
    # print(l, r)
    for k in range(1, N+1+1):
        # print('{}C{}={}'.format(l+N-r, k-1, c2))
        ret.append((c1 - c2 + MOD) % MOD)
        c1 = (c1 * (N+1-k) // (k+1)) % MOD
        c2 = (c2 * ((l+r)-(k-1)) // k) % MOD

    return ret


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _11(N, A)
    print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
def _11(N: int, A: list)->list:
    MOD = 10**9 + 7

    d = {}
    l, r = 0, 0
    for i, a in enumerate(A):
        if a in d:
            l, r = d[a], i
        else:
            d[a] = i

    c1, c2 = N+1, 1
    ret = []
    # print(l, r)
    for k in range(1, N+1+1):
        # print('{}C{}={}'.format(l+N-r, k-1, c2))
        ret.append((c1 - c2 + MOD) % MOD)
        c1 = (c1 * (N+1-k) // (k+1)) % MOD
        c2 = (c2 * (l+N-r-k+1) // k) % MOD

    return ret


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _11(N, A)
    print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
def _11(N: int, A: list)->list:
    MOD = 10**9 + 7

    d = {}
    l, r = 0, 0
    for i, a in enumerate(A):
        if a in d:
            l, r = d[a], i
        else:
            d[a] = i

    c1, c2 = N+1, 1
    ret = []
    print(l, r)
    for k in range(1, N+1):
        # print('{}C{}={}'.format(l+N-r, k-1, c2))
        ret.append((c1 - c2 + MOD) % MOD)
        c1 = (c1 * (N+1-k) // (k+1)) % MOD
        c2 = (c2 * (l+N-r-k+1) // k) % MOD

    return ret


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _11(N, A)
    print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
def _11(N: int, A: list)->list:
    MOD = 10**9 + 7

    d = {}
    l, r = 0, 0
    for i, a in enumerate(A):
        if a in d:
            l, r = d[a], i
        else:
            d[a] = i

    c1, c2 = N+1, 1
    ret = []
    print(l, r)
    for k in range(1, N+2):
        # print('{}C{}={}'.format(l+N-r, k-1, c2))
        ret.append((c1 - c2 + MOD) % MOD)
        c1 = (c1 * (N+1-k) // (k+1)) % MOD
        c2 = (c2 * (l+N-r-k+1) // k) % MOD

    return ret


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _11(N, A)
    print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
def _11(N: int, A: list)->list:
    MOD = 10**9 + 7

    d = {}
    dup1, dup2 = 0, 0
    for i, a in enumerate(A):
        if a in d:
            dup1, dup2 = d[a], i
        else:
            d[a] = i

    c1, c2, c3 = N+1, 1, 0
    ret = []
    for k in range(1, N+2):
        ret.append((c1 - c2 - dup1*c3 + MOD) % MOD)
        c1 = (c1 * (N+1-k) // (k+1)) % MOD
        c2 = (c2 * (N-dup2-k+1) // k) % MOD
        c3 = 1 if k+1 == 2 else (c3 * (N-dup2-k+2)//(k-1)) % MOD

    return ret


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _11(N, A)
    print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
idx=dict()
mod=10**9+7
for i in range(1+n):
    if A[i] in idx:
        x=idx[A[i]]
        y=i
        break
    idx[A[i]]=i
gawa=n-1-(y-x-1)
zentai=n-1
gawa_conb=[1]
for i in range(1,1+gawa):
    if i<1+gawa//2:
        gawa_conb.append((gawa_conb[-1]*(gawa-i+1)//i)%mod)
    else:
        gawa_conb.append(gawa_conb[gawa-i])
gawa_conb+=[0]*(zentai-gawa)
zentai_conb=[1]
for i in range(1,1+zentai):
    if i<1+zentai//2:
        zentai_conb.append((zentai_conb[-1]*(zentai-i+1)//i)%mod)
    else:
        zentai_conb.append((zentai_conb[zentai-i]))
if n>1:
    print((zentai_conb[1]+zentai_conb[0]*2-gawa_conb[0])%mod)
    for i in range(2,n):
        print((zentai_conb[i-2]+zentai_conb[i]+zentai_conb[i-1]*2-gawa_conb[i-1])%mod)
    print((zentai_conb[n-2]+zentai_conb[n-1]*2-gawa_conb[n-1])%mod)
    print((zentai_conb[n-1])%mod)
else:
    print(1)
    print(1)

Submission status: Wrong Answer

Solution code:
import math
import collections

mod = 10 ** 9 + 7

def nCr(n, r):
    return (math.factorial(n) % mod) // ((math.factorial(n - r) % mod) * (math.factorial(r) % mod))


n = int(input())
a = list(map(int, input().split()))
w = collections.Counter(a).most_common(1)[0][0]
w_index = []
for i in range(n + 1):
    if a[i] == w:
        w_index.append(i)
for i in range(1, n + 2):
    if w_index[0] + n - w_index[1] >= i - 1:
        print((nCr(n + 1, i) % mod - nCr(w_index[0] + n - w_index[1], i - 1) % mod) % mod)
    else:
        print(nCr(n + 1, i) % mod)

Submission status: Wrong Answer

Solution code:
import math
import collections


def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
w = collections.Counter(a).most_common(1)[0][0]
w_index = []
for i in range(n + 1):
    if a[i] == w:
        w_index.append(i)
for i in range(1, n + 2):
    if w_index[0] + n - w_index[1] >= i - 1:
        print((nCr(n + 1, i) % mod - nCr(w_index[0] + n - w_index[1], i - 1) % mod) % mod)
    else:
        print(nCr(n + 1, i))

Submission status: Wrong Answer

Solution code:
import math
import collections


def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n = int(input())
a = list(map(int, input().split()))
w = collections.Counter(a).most_common(1)[0][0]
w_index = []
for i in range(n + 1):
    if a[i] == w:
        w_index.append(i)
for i in range(1, n + 2):
    if w_index[0] + n - w_index[1] >= i - 1:
        print(nCr(n + 1, i) - nCr(w_index[0] + n - w_index[1], i - 1))
    else:
        print(nCr(n + 1, i))

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

li=list(map(int,input().split()))
cl=[0]*N
for i in range(N+1):
    cl[li[i]-1]+=1
hu=0
for i in range(N):
    if cl[i]==2:
        hu=i+1
h1=-1
h2=-1
for i in range(N+1):
    if h1==-1 and li[i]==hu:
        h1=i
    if h1>=0 and li[i]==hu:
        h2=N-i

print(N)
for i in range(N):
    print((cmb(N+1,i+2,mod)-cmb(h1,i+1,mod)-cmb(h2,i+1,mod))%mod)

Submission status: Wrong Answer

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

class ModInv:
    def __init__(self, size, MOD):
        self.inv = [0] * (size + 1)
        self.inv[1] = 1
        for i in range(2, size + 1):
            self.inv[i] = (-(MOD // i) * self.inv[MOD%i]) % MOD

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

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        break

first = a.index(b[i])
for i in range(first + 1, n + 1):
    if a[i] == a[first]:
        second = i

w = n + first - second

inv = ModInv(n + 1, MOD)
c = [1] * (n + 2)
d = [1] * (n + 2)

for i in range(n + 1):
    d[i + 1] = (d[i] * inv.inv[i + 1]) % MOD
for i in range(n + 1):
    c[i + 1] = (c[i] * (i + 1)) % MOD

print(n)
for k in range(2, n + 2):
    ans = (((c[n+1] * d[n+1-k]) % MOD) * d[k]) % MOD
    if w >= k - 1:
        ans -= (((c[w] * d[w-k+1]) % MOD) * d[k-1]) % MOD
    print( ans )

Submission status: Wrong Answer

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

class ModInv:
    def __init__(self, size, MOD):
        self.inv = [0] * (size + 1)
        self.inv[1] = 1
        for i in range(2, size + 1):
            self.inv[i] = (-(MOD // i) * self.inv[MOD%i]) % MOD

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

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        break

first = a.index(b[i])
for i in range(first + 1, n + 1):
    if a[i] == a[first]:
        second = i

w = n + first - second

inv = ModInv(n + 1, MOD)
c = [1] * (n + 2)
d = [1] * (n + 2)

for i in range(n + 1):
    d[i + 1] = (d[i] * inv.inv[i + 1]) % MOD
for i in range(n + 1):
    c[i + 1] = (c[i] * (i + 1)) % MOD

print(n)
for k in range(2, n + 2):
    if w >= k - 1:
        print( ((((c[n+1] * d[k]) % MOD) * d[n+1-k]) % MOD) - ((((c[w] * d[k-1]) % MOD) * d[w-k+1]) % MOD) )
    #elif w == k - 1:
     #   print((((c[n+1] * d[k]) % MOD) * d[n+1-k]) % MOD - 1)
    else:
        print( (((c[n+1] * d[k]) % MOD) * d[n+1-k]) % MOD )

Submission status: Wrong Answer

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

class ModInv:
    def __init__(self, size, MOD):
        self.inv = [0] * (size + 1)
        self.inv[1] = 1
        for i in range(2, size + 1):
            self.inv[i] = (-(MOD // i) * self.inv[MOD%i]) % MOD

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

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        break

first = a.index(b[i])
for i in range(first + 1, n + 1):
    if a[i] == a[first]:
        second = i

w = n + first - second

inv = ModInv(n + 1, MOD)
c = [1] * (n + 2)
d = [1] * (n + 2)

for i in range(n + 1):
    d[i + 1] = (d[i] * inv.inv[i + 1]) % MOD
for i in range(n + 1):
    c[i + 1] = (c[i] * (i + 1)) % MOD

print(n)
for k in range(2, n + 2):
    if w > k - 1:
        print( ((((c[n+1] * d[k]) % MOD) * d[n+1-k]) % MOD) - ((((c[w] * d[k-1]) % MOD) * d[w-k+1]) % MOD) )
    elif w == k - 1:
        print((((c[n+1] * d[k]) % MOD) * d[n+1-k]) % MOD - 1)
    else:
        print( (((c[n+1] * d[k]) % MOD) * d[n+1-k]) % MOD )

Submission status: Wrong Answer

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

class ModInv:
    def __init__(self, size, MOD):
        self.inv = [0] * (size + 1)
        self.inv[1] = 1
        for i in range(2, size + 1):
            self.inv[i] = (-(MOD // i) * self.inv[MOD%i]) % MOD

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

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        d = b[i]
        break

first = a.index(d)
for i in range(first + 1, n + 1):
    if a[i] == d:
        second = i

w = n + first - second

inv = ModInv(n + 1, MOD)
c = [1] * (n + 2)
d = [1] * (n + 2)

for i in range(n + 1):
    d[i + 1] = (d[i] * inv.inv[i + 1]) % MOD
for i in range(n + 1):
    c[i + 1] = (c[i] * (i + 1)) % MOD

print(n)
for k in range(2, n + 2):
    if k < w:
        print( (((c[n+1] * d[k]) * d[n+1-k]) % MOD) - (((c[w] * d[k]) * d[w-k]) % MOD) )
    else:
        print( ((c[n+1] * d[k]) * d[n+1-k]) % MOD )

Submission status: Wrong Answer

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



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 + 2 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


sorted_a=sorted(a)
for i in range(n):
  if sorted_a[i]==sorted_a[i+1]:
    num = sorted_a[i]
    break

flag = True
for i in range(n+1):
  if a[i]==num:
    if flag:
      first = i
      flag = False
    else:
      second = i

#combination=[0]*(n+2)
#combination[0]=1
#for i in range(1,n+2):
#  combination[i] =combination[i-1]*(n+2-i)//i
#combination2=[0]*(n+2)
#combination2[0]=0
#combination2[1]=1
#for i in range(2,n+2):
#  combination2[i] =combination2[i-1]*(first+n-second+1-(i-1))//(i-1)

#for i in range(1,n+2):
  #ans = comb(n-1,i) + 2*comb(n-1,i-1)-comb(first+n-second,i-1) +comb(n-1,i-2)
  #ans = comb(n+1,i) - comb(first+n-second,i-1)
  #ans = (combination[i]%1000000007-combination2[i]%1000000007)%1000000007
  #print(ans)  
  
for i in range(1,n+2):
  ans = cmb(n+1,i,mod) - cmb(first+n-second,i-1,mod)
  print(ans)