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:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


class Combination:
    def __init__(self, n, mod):
        assert 0 < n
        self.mod = mod
        self.fact = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for i in range(1, len(self.fact)):
            self.fact[i] = (i * self.fact[i - 1]) % self.mod
            self.inv[i] = pow(self.fact[i], self.mod - 2, self.mod)

    def nCr(self, n, k):
        assert 0 <= n < len(self.fact) and 0 <= k
        assert n >= k
        a = self.fact[n]
        b = (self.inv[k] * self.inv[n - k]) % self.mod
        return a * b % self.mod


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

    comb = Combination(10**5 + 10, MOD)

    pos = [-1] * 100010
    for i, a in enumerate(A):
        if pos[a] != -1:
            pos1, pos2 = min(pos[a], i), max(pos[a], i)
            break
        pos[a] = i

    dist = pos2 - pos1
    for i in range(1, N + 2):
        ans = comb.nCr(N + 1, i)
        if i <= dist and N + 1 - dist - 1 >= i - 1:
            ans -= comb.nCr(N + 1 - dist - 1, i - 1)

        print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def factorial_memo(n, p):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F

def inverse(F, p):
  Finv = [x for x in F]
  Finv[-1] = pow(Finv[-1], p - 2, p)
  for i in range(len(F) - 2, 0, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv

def comb(a, b):
  if a < b:
    return 0
  return F[a] * Finv[a - b] * Finv[b] % p

n = int(input())
A = [int(x) for x in input().split()]
p = 10 ** 9 + 7
D = [-1] * n
double = [-1, -1]
for i, a in enumerate(A):
  if D[a - 1] == -1:
    D[a - 1] = i
  else:
    double = [D[a - 1], i]
    break
F = factorial_memo(n + 1, p)
Finv = inverse(F, p)
n_a = double[0]
n_b = n - double[1]
print(n)
C = [0] * n
for i in range(2, n + 2):
  cnt = (comb(n, i) + comb(n, i - 1) - max((n_a + n_b + 2 - i), 0)) % p
  print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


# --------------------------------------------

dp = None


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


class Combination:
    def __init__(self, n, mod=(10**9 + 7)):

        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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

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


def main():
    N = int(input())
    A = li_input()

    C = Combination(N + 1)

    double_elem = sum(A) - sigma(N)

    l, r = -1, -1

    for i, a in enumerate(A, start=1):
        if a == double_elem:
            if l == -1:
                l = i
            else:
                r = i
                break

    for i in range(1, N + 2):
        print(C(N + 1, i) - C(l - 1 + N + 1 - r, i - 1))


main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


# --------------------------------------------

dp = None


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


class Combination:
    def __init__(self, n, mod=(10**9 + 7)):

        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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

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


def main():
    N = int(input())
    A = li_input()

    C = Combination(N + 1)

    double_elem = sum(A) - sigma(N)

    l, r = -1, -1

    for i, a in enumerate(A, start=1):
        if a == double_elem:
            if l == -1:
                l = i
            else:
                r = i
                break

    for i in range(1, N + 2):
        print(C(N + 1, i) - C(l - 1 + N + 1 - r, i - 1))


main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


# --------------------------------------------

dp = None


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def nCk(n, k):
    if k == 0:
        return 1

    if n == 0:
        return 0

    if n < k:
        return 0

    a, b = 1, 1

    k = min(k, n - k)

    for aa in range(n, n - k, -1):
        a *= aa

    for bb in range(1, k + 1):
        b *= bb

    return a // b


def main():
    N = int(input())
    A = li_input()

    double_elem = sum(A) - sigma(N)

    l, r = -1, -1

    for i, a in enumerate(A, start=1):
        if a == double_elem:
            if l == -1:
                l = i
            else:
                r = i
                break

    for i in range(1, N + 2):
        print(nCk(N + 1, i) - nCk(l - 1 + N + 1 - r, i - 1))


main()

Submission status: Wrong Answer

Solution code:
#list_int 並べて出力 print (' '.join(map(str,ans_li)))
#list_str 並べて出力 print (' '.join(list))

# 2進数 format(10, 'b') # '1010'

# aa=[int(input()) for i in range(n)]

#for i,name in enumerate(list)

''' 二次元配列を一列ずつ
for i in ans:
	print(*i)
'''
''' heapq
queue = []
heapq.heapify(queue) #heapqの作成
heapq.heappush(queue,num) #numのpush(値の追加)
pop = heapq.heappop(queue) #numのpop(最小値の出力)
pop = heapq.heappushpop(queue,num) #push -> pop

'''

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl_int(): return list(map(int, input().split()))
def inpl_str(): return list(map(int, input().split()))

def Comb(n):
    gyakugen = [1]*(n+1)
    fac = [1]*(n+1)

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

    gyakugen[n] = pow(fac[n],mod-2,mod)

    for i in range(n,0,-1):
        gyakugen[i-1] = (gyakugen[i]*i)%mod

    com = [1]*(n+1)

    for i in range(1,n+1):
        com[i] = (fac[n]*gyakugen[i]*gyakugen[n-i])%mod

    return com

N = int(input())
aa = inpl_int()

i = 1
dd = defaultdict(int)
for i,a in enumerate(aa):
	if dd[a] == 0:
		dd[a] = i+1
	else:
		X1 = dd[a]-1
		X2 = i

L,R = X1,N-X2
ALL = 1

ALL = Comb(N+1)
daburi = Comb(L+R)

for i in range(1,N+2):
	if L+R+1 >= i:
		print(ALL[i]-daburi[i-1])
	else:
		print(ALL[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl_int(): return list(map(int, input().split()))
def inpl_str(): return list(map(int, input().split()))

N = int(input())
aa = inpl_int()

i = 1
while True:
	if aa.count(i)==2:
		X1 = aa.index(i)
		aa[X1] = 0
		X2 = aa.index(i)
		break
	i += 1

print(X1,X2)
L,R = X1,N-X2
ALL = 1

for i in range(1,N+2):
	ALL = ALL * (N+2-i)//i
	if L+R+1 >= i:
		if i == 1:
			daburi = 1
		else:
			daburi = daburi * (L+R+2-i)//(i-1)
	else:
		daburi = 0

	print(i,(ALL-daburi)%mod)

Submission status: Wrong Answer

Solution code:
N = int(input())
e = list(map(int,input().split()))
mod = 1000000007
kai = [0]*(N+3)
from collections import Counter
c = Counter(e).most_common(1)[0][0]
g = e.index(c)
e.remove(c)
f = e.index(c) +1
e = []
for i in range(N+3):
  if i ==0:
    kai[i] = 1
  else:
    kai[i] = (kai[i-1]*(i))%mod
def comb(n,k,p):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=kai[n] 
  b=kai[k] 
  c=kai[n-k] 
  b = pow(b,mod-2,mod)
  c = pow(c,mod-2,mod)
  return (a*b*c)%mod
h = [1]*((N+6)//2)
for j in range((N+4)//2):
  h[j+1] = comb(N+1,j+1,mod)
for j in range(N+1):
  if N-j>N/2:
    print(h[j+1]-comb(g+N-f,j,mod))
  else:
    print(h[N-j]-comb(g+N-f,j,mod))

Submission status: Wrong Answer

Solution code:
# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


n = int(input())
A = list(map(int, input().split()))
C = [-1] * (n+1)
lr = 0
for i, a in enumerate(A):
    if C[a] == -1:
        C[a] = i
    else:
        lr = C[a] + n - i
        break


def combination(n):
    lst = [1]
    mod = 10**9+7
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst


NC = combination(n+1)
LRC = combination(lr)
for i in range(1, n+2):
    print(NC[i] - (LRC[i-1] if i-1 <= lr else 0))

Submission status: Wrong Answer

Solution code:
# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

      
n = int(input())
A = list(map(int, input().split()))
C = [-1] * (n+1)
lr = 0
for i, a in enumerate(A):
    if C[a] == -1:
        C[a] = i
    else:
        lr = C[a] + n - i
        break


def combination(n):
    lst = [1]
    mod = 10**9+7
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) * modinv(i, mod) % mod)
    return lst


NC = combination(n+1)
LRC = combination(lr)
for i in range(1, n+2):
    print(NC[i] - (LRC[i-1] if i-1 <= lr else 0))

Submission status: Wrong Answer

Solution code:
def comb(n,k):
	if n<k or n==0: return 0
	elif k==0: return 1
	else: return f[n]*p[k]*p[n-k]%(10**9+7)
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
twice = Counter(a).most_common(1)[0][0]
x,y = (i for i,j in enumerate(a) if j == twice)
num,y,f,p = 1,n-y,[1],[1]
for i in range(1,n+2):
	f.append(f[-1]*i%(10**9+7))
	p.append(pow(f[-1],10**9+5,10**9+7))
for i in range(1,x+y+2): print((comb(n+1,i)-comb(x+y,i-1))%(10**9+7))
for i in range(x+y+2,n+2): print(comb(n+1,i))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

ctr = Counter(src)
most = ctr.most_common(1)[0][0]
i1 = src.index(most)
i2 = src[i1+1:].index(most) + i1+1
d = i2 - i1

MOD = 10**9+7

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,N+3):
    f = mul(fac[n-1], n)
    fac.append(f)
    fac_inv.append(inv(f))

def ncr(n,r):
    return mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])

anss = []
for r in range(1,N+2):
    anss.append(ncr(N+1,r))
n = N-d
for r in range(n+1):
    anss[r] -= ncr(n,r)

print(*anss, sep='\n')

Submission status: Wrong Answer

Solution code:
from statistics import mode

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

# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

# 階乗の値を保存
factorial = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1]*i % MOD)

# 逆元を保存
inverse = [0]
for i in range(N+2-2, -1, -1):
    inverse.append(pow(i, MOD-2, MOD))


# combination計算
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 k in range(1, len(A) + 1):
    if k > outside + 1:
        Y = pow(factorial[k] * factorial[N+1-k] % MOD, MOD - 2, MOD)
        print((factorial[-1] * Y) % MOD)
    else:
        Y = pow(factorial[k] * factorial[N+1-k] % MOD, MOD - 2, MOD)
        Y2 = pow(factorial[k-1] * factorial[outside - k + 1] % MOD, MOD - 2, MOD)
        print(((factorial[-1] * Y) % MOD - (factorial[outside] * Y2) % MOD))

Submission status: Wrong Answer

Solution code:
from statistics import mode

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

# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

# 階乗の値を保存
factorial = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1]*i % MOD)

# 逆元を保存
inverse = [0] * (N+2)
inverse[N+2-1] = pow(factorial[N+2-1], MOD-2, MOD)
for i in range(N+2-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % MOD


# combination計算
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 k in range(1, len(A) + 1):
    if k > outside + 1:
        Y = pow(factorial[k] * factorial[N+1-k] % MOD, MOD - 2, MOD)
        print((factorial[-1] * Y) % MOD)
    else:
        Y = pow(factorial[k] * factorial[N+1-k] % MOD, MOD - 2, MOD)
        Y2 = pow(factorial[k-1] * factorial[outside - k + 1] % MOD, MOD - 2, MOD)
        print(((factorial[-1] * Y) % MOD - (factorial[outside] * Y2) % MOD))

Submission status: Wrong Answer

Solution code:
from statistics import mode
from scipy.misc import comb

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9

# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

for k in range(1, len(A)+1):
    if k > outside + 1:
        print(comb((N+1), k, exact=True) % MOD)
    else:
        print(comb((N+1), k, exact=True) % MOD - comb(outside, (k-1), exact=True) % MOD)

Submission status: Wrong Answer

Solution code:
def c_pushpush(N,A):
    from collections import deque
    # insertをリストの先頭に行うと、リストの要素の再配置に時間がかかる
    b = deque([])
    n_parity = N & 1
    for i in range(N):
        if n_parity == (i + 1) & 1:
            # n,iのパリティが一致
            b.appendleft(A[i])
        else:
            b.append(A[i])
    ans = ' '.join(map(str,b))
    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(c_pushpush(N,A))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
#重複始点終点調査
se=[]
for i in range(len(A)):
  if A[i]==sum(A)-N*(N+1)/2:
    se.append(i)

mod=10**9+7
 
#階乗計算
factorial=[1]
for i in range(1,N+2):
    factorial.append(factorial[i-1]*i %mod)
#逆元計算
inverse=[0]*(N+2)
inverse[N+2-1] = pow(factorial[N+2-1], mod-2,mod)
for i in range(N+2-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod
#combination計算
def nCr(n,r):
  if n<r or n==0 or r==0:
    return 0
  return factorial[n] * inverse[r] * inverse[n-r] % mod

print(N)
if N==1:
  print(N)
else:
  for i in range(1,N+1):
    ans = nCr(N+1, i+1)
    if se[0] + N -se[1] >= i:
      ans-=nCr(se[0]+N-se[1],i)
      print(int(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
n=input()
a=map(int, raw_input().split())
b=Counter(a)
freq_val=b.most_common(1)[0][0]


g =[math.factorial(i) for i in range(n+2) ]
def combination(x,r):
    	return int(g[x]/(g[r]*g[x-r]))


index_num=[n for n, v in enumerate(a) if v==freq_val]
d=index_num[1]-index_num[0]


for k in range(1,n+2):
	print combination(n+1,k)-combination(n-d,k-1)

Submission status: Wrong Answer

Solution code:
import collections
n=input()
a=map(int, raw_input().split())
#print n
#print a
len_a=len(a)
dp=[[0]*(len_a+1) for _ in range(len_a+1)]


for i in range(1,len_a+1):
	dp[i][1]=len(set(a[:i]))

#print dp

for j in range(1,len_a+1):
	for k in range(1,len_a+1):
			if j>=k:
				if k==1:
					pass
				else:
					dp[j][k]=dp[j-1][k]+dp[j-1][k-1]

#print dp
#print dp[len_a]

for i in range( 1,len(dp[len_a]) ):
	print dp[len_a][i]

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, combinations
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


class Combination:
    def __init__(self, n, mod):
        assert 0 < n
        self.mod = mod
        self.fact = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for i in range(1, len(self.fact)):
            self.fact[i] = (i * self.fact[i - 1]) % self.mod
            self.inv[i] = pow(self.fact[i], self.mod - 2, self.mod)

    def nCr(self, n, k):
        assert 0 < n < len(self.fact) and 0 <= k, (n, k)
        a = self.fact[n]
        b = (self.inv[k] * self.inv[n - k]) % self.mod
        return a * b % self.mod


def main():
    n = int(input())
    a_list = list(map(int, input().split()))

    dual = Counter(a_list).most_common(1)[0][0]
    pre, post = [i for i, a in enumerate(a_list) if a == dual]
    x = pre + (n - post)

    comb = Combination(10 ** 5 + 1, 10 ** 9 + 7)
    for i in range(1, n + 2):
        a, b = comb.nCr(n + 1, i), 0
        if i == 1:
            b = 1
        elif 0 < x and i - 1 <= x:
            b = comb.nCr(x, i - 1)
        print(a - b)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = int(1e9 + 7)

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

factorial = [1] * (N + 2)
for k in range(1, N + 2):
    factorial[k] = (factorial[k - 1] * k) % MOD

fact_inv = [1] * (N + 2)
fact_inv[N + 1] = pow(factorial[N + 1], MOD - 2, MOD)
for k in range(N, -1, -1):
    fact_inv[k] = (fact_inv[k + 1] * (k + 1)) % MOD

def comb(n, r):
    if r>n or n<0 or r<0:
        return 0
    else:
        return (factorial[n] * fact_inv[n-r] * fact_inv[r]) % MOD
    
L,R = -1,-1
ls = set()
for i in range(N+1):
    if A[i] in ls:  
        R = i + 1
        L = A.index(A[i]) + 1
        break
    else:
        ls.add(A[i])


[print( comb(N+1,i) - comb(L+N-R,i-1) ) for i in range(1,N+2)  ]

Submission status: Wrong Answer

Solution code:
MOD = int(1e9 + 7)

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

factorial = [1] * (N + 2)
for k in range(1, N + 2):
    factorial[k] = (factorial[k - 1] * k) % MOD

fact_inv = [1] * (N + 2)
fact_inv[N + 1] = pow(factorial[N + 1], MOD - 2, MOD)
for k in range(N, -1, -1):
    fact_inv[k] = (fact_inv[k + 1] * (k + 1)) % MOD

def comb(n, r):
    if r>n:
        return 0
    else:
        return (factorial[n] * fact_inv[n-r] * fact_inv[r]) % MOD
    
L,R = -1,-1
ls = []
for i in range(N+1):
    if A[i] in ls:
        R = i + 1
        L = ls.index(A[i]) + 1
        break
    else:
        ls.append(A[i])

[print( comb(N+1,i) - comb(L+N-R,i-1) ) for i in range(1,N+2)  ]

Submission status: Wrong Answer

Solution code:
def D_11(x):
    n = x[0]  # 整数の数
    a = x[1:]  # 数列
    M = 10**9 + 7  # 求めた解の剰余をこれで取る

    # aの中から重複した要素のインデックス(それぞれl,rとする)を求める
    import collections
    freq = collections.Counter(a).most_common(1)  # 最も多く出てきた数(入力の制約より、頻度は2となる)
    index = [i for i, x in enumerate(a) if x == freq[0][0]]  # 重複した数のインデックスを取得
    l, r = index[0] + 1, index[1] + 1  # +1するのは数列が1スタートのため

    # 組み合わせの計算
    def power(x, n, m):
        # 冪乗(powだと時間がかかりすぎるため)+剰余つき
        y = 1
        while n > 0:
            if n % 2 == 0:
                x = (x * x) % m
                n = n // 2
            else:
                y = (y * x) % m
                n -= 1
        return y

    # この部分は関数の外に出しておかないと、呼び出しのたびに計算して遅い
    factrial = [1] * (n + 2)
    inverse = [1] * (n + 2)
    for i in range(1, n + 2, 1):
        factrial[i] = (factrial[i - 1] * i) % M
        inverse[i] = power(factrial[i], M - 2, M) % M # フェルマーの小定理からの帰結

    def mod_combination(n, r, m):
        if r > n or n < 0 or r < 0:
            return 0
        else:
            return (factrial[n] * inverse[r] * inverse[n - r]) % m
    for k in range(1, n + 2, 1):
        all_comb = mod_combination(n + 1, k, M) % M
        duplication = mod_combination(l + n - r, k - 1, M) % M
        print(all_comb - duplication)

n = int(input())
l = [int(i) for i in input().split()]
x = [n] + l
D_11(x)

Submission status: Wrong Answer

Solution code:
def D_11(x):
    n = x[0]  # 整数の数
    a = x[1:]  # 数列
    M = pow(10, 9) + 7  # 求めた解の剰余をこれで取る

    # aの中から重複した要素のインデックス(それぞれl,rとする)を求める
    import collections
    freq = collections.Counter(a).most_common(1)  # 最も多く出てきた数(入力の制約より、頻度は2となる)
    index = [i for i, x in enumerate(a) if x == freq[0][0]]  # 重複した数のインデックスを取得
    l, r = index[0] + 1, index[1] + 1  # +1するのは数列が1スタートのため

    # 組み合わせの計算
    def power(x, n, m):
        # 冪乗(powだと時間がかかりすぎるため)+剰余つき
        y = 1
        while n > 0:
            if n % 2 == 0:
                x = (x * x) % m
                n = n // 2
            else:
                y = (y * x) % m
                n -= 1
        return y

    # この部分は関数の外に出しておかないと、呼び出しのたびに計算して遅い
    factrial = [1] * (n + 2)
    inverse = [1] * (n + 2)
    for i in range(1, n + 2, 1):
        factrial[i] = (factrial[i - 1] * i) % M
        inverse[i] = power(factrial[i], M - 2, M)  # フェルマーの小定理からの帰結

    def mod_combination(n, r, m):
        if r > n or n < 0 or r < 0:
            return 0
        else:
            return (factrial[n] * inverse[r] * inverse[n - r]) % m
    for k in range(1, n + 2, 1):
        all_comb = mod_combination(n + 1, k, M)
        duplication = mod_combination(l + n - r, k - 1, M)
        print(all_comb - duplication)

n = int(input())
l = [int(i) for i in input().split()]
x = [n] + l
D_11(x)

Submission status: Wrong Answer

Solution code:
def D_11(x):
    n = x[0]  # 整数の数
    a = x[1:]  # 数列

    # aの中から重複した要素のインデックス(それぞれl,rとする)を求める
    import collections
    freq = collections.Counter(a).most_common(1)  # 最も多く出てきた数(入力の制約より、頻度は2となる)
    index = [i for i, x in enumerate(a) if x == freq[0][0]]  # 重複した数のインデックスを取得
    l, r = index[0] + 1, index[1] + 1  # +1するのは数列が1スタートのため

    # 組み合わせの計算
    import scipy.misc as scm
    for k in range(1, n + 2, 1):
        combination = scm.comb((n + 1), k,1)
        duplication = scm.comb((l - 1) + (n - r), (k - 1),1)
        print((combination - duplication)%(pow(10,9)+7))

n = int(input())
l = [int(i) for i in input().split()]
x = [n] + l
D_11(x)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from collections import Counter
import re

def pow(a, x):
        y = 1
        p = a % mask
        n = x
        while (n > 0):
                if ((n % 2) == 0):
                        p = (p * p) % mask
                        n /= 2
                else:   
                        y = (y * p) % mask
                        n -= 1
        return y

n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0

mask = 10**9 + 7
invm = 10**9 + 5

com = [1]*(n+2)
inv = [1]*(n+2)

tmp = 1
for i in range(1, n+2):
        tmp = (tmp * i) % mask
        com[i] = tmp
        inv[i] = pow(tmp, invm) % mask

counter = Counter(a)
dup = counter.most_common(1)[0][0]
left = a.index(dup)
right = a[left+1:].index(dup) + left + 1

for i in range(1, n + 2):
        ans = (com[n + 1] * (inv[i] * inv[n + 1 - i])) % mask

#       if ((left + n - right - i + 1) >= 0):
        if ((right - left) >= i):
                ans -= (com[left + n - right] * inv[i - 1] * inv[left + n - right - i + 1]) % mask
        print ans