Problem:


Score : 600 points

Problem Statement

You are given an integer sequence of length n+1, a_1,a_2,...,a_{n+1}, which consists of the n integers 1,...,n.
It is known that each of the n integers 1,...,n appears at least once in this sequence.

For each integer k=1,...,n+1, find the number of the different subsequences (not necessarily contiguous) of the given sequence with length k, modulo 10^9+7.

Notes

If the contents of two subsequences are the same, they are not separately counted even if they originate from different positions in the original sequence.

A subsequence of a sequence a with length k is a sequence obtained by selecting k of the elements of a and arranging them without changing their relative order. For example, the sequences 1,3,5 and 1,2,3 are subsequences of 1,2,3,4,5, while 3,1,2 and 1,10,100 are not.

Constraints

1 \leq n \leq 10^5

1 \leq a_i \leq n

Each of the integers 1,...,n appears in the sequence.

n and a_i are integers.

Input

Input is given from Standard Input in the following format:

n
a_1 a_2 ... a_{n+1}

Output

Print n+1 lines.
The k-th line should contain the number of the different subsequences of the given sequence with length k, modulo 10^9+7.

Sample Input 1

3
1 2 1 3

Sample Output 1

3
5
4
1

There are three subsequences with length 1: 1 and 2 and 3.

There are five subsequences with length 2: 1,1 and 1,2 and 1,3 and 2,1 and 2,3.

There are four subsequences with length 3: 1,1,3 and 1,2,1 and 1,2,3 and 2,1,3.

There is one subsequence with length 4: 1,2,1,3.

Sample Input 2

1
1 1

Sample Output 2

1
1

There is one subsequence with length 1: 1.

There is one subsequence with length 2: 1,1.

Sample Input 3

32
29 19 7 10 26 32 27 4 11 20 2 8 16 23 5 14 6 12 17 22 18 30 28 24 15 1 25 3 13 21 19 31 9

Sample Output 3

32
525
5453
40919
237336
1107568
4272048
13884156
38567100
92561040
193536720
354817320
573166440
818809200
37158313
166803103
166803103
37158313
818809200
573166440
354817320
193536720
92561040
38567100
13884156
4272048
1107568
237336
40920
5456
528
33
1

Be sure to print the numbers modulo 10^9+7.



Sample input:
3
1 2 1 3


Sample output:
3
5
4
1

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

struct Mod {
    static constexpr auto kMod = 1000000007L;
 
    // can be implicitly converted
    Mod(int64_t n) : n(n) {}
 
    Mod operator*(Mod m) const { return (n * (m.n % kMod)) % kMod; }
 
    Mod& operator*=(Mod m) {
        *this = *this * m;
        return *this;
    }
 
    Mod pow(int64_t p) {
        if (p == 0) {
            return 1;
        }
        if (p == 1) {
            return n;
        }
 
        int64_t r = this->pow(p / 2).n;
        if (p % 2 == 0) {
            return r * r % kMod;
        } else {
            return (r * r % kMod) * n % kMod;
        }
    }
 
    Mod operator/(Mod m) const {
        if (n == 0) {
            return 0;
        }
 
        return *this * m.pow(kMod - 2);
    }
 
    Mod& operator/=(Mod m) {
        *this = *this / m;
        return *this;
    }
 
    Mod operator+(Mod m) const { return (n + m.n) % kMod; }
 
    Mod& operator+=(Mod m) {
        *this = *this + m;
        return *this;
    }
 
    Mod operator-(Mod m) const { return (kMod + n - m.n) % kMod; }
 
    Mod& operator-=(Mod m) {
        *this = *this - m;
        return *this;
    }
 
    int64_t n;
};

Mod combi(int64_t a, int64_t b) {
  Mod c(1);
  
  for (auto i : irange(0L, b)) {
    c *= a - i;
    c /= i + 1;
  }
  
  return c;
}

main() {
  int64_t n;
  cin >> n;
  unordered_map<int64_t, int64_t> a;
  int64_t dist = -1;
  for (auto i : irange(0L, n + 1)) {
    int64_t aa;
    cin >> aa;
    if (a.count(aa) > 0) {
      dist = i - a[aa];
    }
    a[aa] = i;
  }
  
  Mod c = 1; // C(n + 1, 0)
  Mod d = 1; // C(n - dist, 0)
  for (auto k : irange(1L, n + 2)) {
    // C(n + 1, k) = C(n + 1, k - 1) * (n - k + 2) / k
    c *= n - k + 2;
    c /= k;
    // C(n - dist, k - 1) = C(n - dist, k - 2) * (n - dist - k + 2) / (k - 1)
    if (k >= 2) {
        d *= n - dist - k + 2;
        d /= k - 1;
    }
    if (k - 1 <= n - dist) {
      cout << (c - d).n << endl;
    } else {
      cout << c.n << endl;
    }
  }
}

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]
mod = 10**9 + 7

f = [1] * (N + 2)
fi = [1] * (N + 2)
for i in range(2, N + 2):
    f[i] = i * f[i - 1]
    f[i] %= mod
for i in range(2, N + 2):
    fi[i] = fi[i - 1] * pow(i, mod - 2, mod)
    fi[i] %= mod


def comb(n, r):
    if 0 <= n and 0 <= r and 0 <= n - r:
        return (f[n] * fi[r] * fi[n - r]) % mod
    else:
        return 0


b = set()
for a in A:
    if a in b:
        break
    b.add(a)
c = []
for i in range(N):
    if A[i] == a:
        c += [i]
i, j = c
for x in range(1, N + 2):
    print((comb(N + 1, x) - (comb(N - j + i, x - 1))) % mod)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

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

#def nCr(n,r):
#  numerator = math.factorial(n)
#  denominator = math.factorial(r) * math.factorial(n-r)
#  return numerator//denominator

A_duplicate = [x for x in set(A) if A.count(x) > 1]
A_duplicate_indexes = [i for i, x in enumerate(A) if x == A_duplicate[0]]

l = A_duplicate_indexes[0]
r = A_duplicate_indexes[1]

for i in range(1,N+2):
  l_count = 0
  r_count = 0
  if l-1 >= i-1:
    l_count = comb(l-1,i-1,exact=True)
  if N-r >= i-1:
    r_count = comb(N-r,i-1,exact=True)

  ans = comb(N+1,i,exact=True) - ( l_count + r_count )
  print(ans%(10**9+7))

Submission status: Runtime Error

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

def comb(n, k):
    if n < k:
        return 0
    ret = 1
    c = min(k, n-k)
    for i in range(c):
        ret *= (n-i)
    for i in range(c):
        ret /= (c-i)
    return ret

li = [0]*(n+1)
twice = 0
for i in range(len(a)):
    li[a[i]] += 1
    if li[a[i]] == 2:
        twice = a[i]
        break

first = -1
second = -1
for i in range(len(a)):
    if first == -1 and a[i] == twice:
        first = i
    elif a[i] == twice:
        second = i



for k in range(1, n+2):
    print((comb(n+1,k) - comb(n+1 - (second - first + 1), k-1)) % 1000000007)

Submission status: Runtime Error

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

    def __init__(self, mod= 10**9+7, max_n = 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: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
N = int(input())
li =  [ int(it) -1 for it in input().split() ] 

from functools import lru_cache
MOD = 1000000007
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
@lru_cache(maxsize=None)
def modinv(a):
    (inv, q, gcd_val) = egcd(a, MOD)
    return inv % MOD
@lru_cache(maxsize=None)
def factorial(k):
  if (k<=1):
    return 1
  return (factorial(k-1)*k)%MOD
@lru_cache(maxsize=None)
def combination(n,m):
  return (factorial(n)*modinv(factorial(m))*modinv(factorial(n-m)))%MOD

#print ( factorial(5),factorial(3) )
#print ( combination(5,3) )

import collections as col
c = col.Counter( li ).items()
a = [ it for it in c if it[1] == 2][0][0]
p1 = li.index(a)
p2 = li[p1+1:].index(a) + 1 + p1
#print ( p1 , p2 )
H = p1 + (N-p2)
#print ( H )

li=[]
for i in range(1,N+2):
  a =  (combination(N+1,i) - (combination(H,i-1)if (i-1)<=H else 0))%MOD
  li.append(a)
print ( "\n".join( map(str,li) ) )

Submission status: Runtime Error

Solution code:
import numpy as np
import numba as nb

# 基本的に重複がない
# n+1Ck − (n+1)-(r-l+1)Ck−1

MOD = 10**9+7
U = 10**5 + 1

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

@nb.njit
def make_fact(fact,fact_inv):
  for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
  fact_inv[U] = power_mod(fact[U],MOD-2)
  for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n,k):
  if k < 0 or k > n:
    return 0
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x

fact = np.ones(U+1,dtype = np.int64)
fact_inv = np.ones(U+1,dtype = np.int64)
make_fact(fact,fact_inv)

# 重複の起きる場所の間隔だけが問題
n = int(input())
A = [int(x) for x in input().split()]

memo = dict()
d = 0
for i,x in enumerate(A):
  if x in memo:
    d = i - memo[x]
    break
  memo[x] = i

rest = n-d

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

Submission status: Runtime Error

Solution code:
import sys
try:
    from scipy.special import comb
except ModuleNotFoundError:
    from scipy.misc import comb

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

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    m = first + (N - second)
    for i in range(1, N+2):
        ans = comb(N+1, i, exact=True) - comb(m, i-1, exact=True)
        print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from scipy.special import comb

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

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

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

    fact_inv = [1] * (N+2)
    fact_inv[N+1] = pow(factrial[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, MOD):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD
    """

    m = first + (N - second)
    for i in range(1, N+2):
        ans = comb(N+1, i, exact=True) - comb(m, i-1, exact=True)
        print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import factorial

def comb(n, r):
    if r < 0:
        return 0
    if n < r:
        return 0
    if n == r:
        return 1
    return factorial(n) / factorial(r) / factorial(n - r)

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

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    for i in range(1, N+2):
        ans = comb(N+1, i)
        for j in range(i):
            m_f = first
            r_f = j

            m_b = N - second
            r_b = i - (j + 1)

            ans -= comb(m_f, r_f) * comb(m_b, r_b)

        print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import factorial

def comb(n, r):
    if r < 0:
        return 0
    if n < r:
        return 0
    return factorial(n) / factorial(r) / factorial(n - r)

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

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    for i in range(1, N+2):
        ans = comb(N+1, i)
        for j in range(i):
            m_f = first
            r_f = j

            m_b = N - second
            r_b = i - (j + 1)

            ans -= comb(m_f, r_f) * comb(m_b, r_b)

        print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from scipy.special import comb

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

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    for i in range(1, N+2):
        ans = comb(N+1, i)
        for j in range(i):
            m_f = first
            r_f = j

            m_b = N - second
            r_b = i - (j + 1)

            ans -= comb(m_f, r_f) * comb(m_b, r_b)

        print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def mod_inv(n: int, mod: int)->int:
    b, u, v = mod, 1, 0
    while b > 0:
        t = n // b

        n -= t * b
        u -= t * v

        a, b = b, a
        u, v = v, u

    return (u+mod) % mod


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) * mod_inv(i+1, MOD)) % MOD
        c2[i+1] = (c2[i] * (l+r-i) * mod_inv(i+1, MOD)) % 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: Runtime Error

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


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


fact = [1] * int(1e5+1)
for i in range(1, int(1e5+1)):
    fact[i] = (i * fact[i-1]) % mod
inv = [1] * int(1e5+1)
inv[int(1e5)] = power(fact[int(1e5)], mod-2) % mod
for i in range(int(1e5)-1, 0, -1):
    inv[i] = (inv[i+1] * (i+1)) % mod


def combination(n, r):
    return fact[n] * inv[r] * inv[n-r] % mod


def main():
    N = int(input())
    A = list(map(int, input().split()))
    idx = [-1] * (N+1)
    x = 0
    for i in range(N+1):
        if idx[A[i]] == -1:
            idx[A[i]] = i
        else:
            x = i - idx[A[i]]
    for i in range(1, N+2):
        ans = combination(N+1, i)
        if i <= (N+1-x):
            ans = (ans - combination(N+1-(x+1), i-1)) % mod
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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


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


def div(a, b):
    return a * power(b, mod-2) % mod


fact = [1] * int(1e5)
for i in range(1, int(1e5)):
    fact[i] = (i * fact[i-1]) % mod


def combination(n, r):
    return div(div(fact[n], fact[r]), fact[n-r])


def main():
    N = int(input())
    A = list(map(int, input().split()))
    idx = [-1] * (N+1)
    x = 0
    for i in range(N+1):
        if idx[A[i]] == -1:
            idx[A[i]] = i
        else:
            x = i - idx[A[i]]
    for i in range(1, N+2):
        ans = combination(N+1, i)
        if i <= (N+1-x):
            ans = (ans - combination(N+1-(x+1), i-1)) % mod
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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: Runtime Error

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):
    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: Runtime Error

Solution code:
def init_fact(n,mod):
    fact,finv,inv = [1]*n,[1]*n,[1]*n
    for i in range(2,n):
        fact[i] = (fact[i-1]*i) % mod
        inv[i]  = mod - inv[mod%i] * (mod//i)%mod
        finv[i] = finv[i-1] * inv[i] % mod
    return (fact,finv,inv)

def nCr(n,r,mod,fact,finv):
    if n<r:
        return 0
    else:
        return fact[n] * (finv[r] * finv[n-r] % mod) % mod

modulo = 10**9+7
fact,finv,inv = init_fact(200000,modulo)


from collections import Counter
N = int(input())
A = list(map(int,input().split()))

# 重複している数を調べる
C = Counter(A).most_common()
x = C[0][0]

# 重複している数のindexを調べる
xi = []
for i in range(N):
    if A[i]==x:
        xi.append(i)
h = xi[1]-xi[0]+1

for i in range(1,N+2):
    print(nCr(N+1,i,modulo,fact,finv) - nCr(N+1-h,i-1,modulo,fact,finv))

Submission status: Runtime Error

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

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

p = []
for i in range(n):
    if a[i] == d:
        p.append(i)

w = p[0] + n - p[1]

c = [0 for _ in range(n + 2)]
d = [0 for _ in range(n + 2)]

L = 1
H = 1
for i in range(1, n + 2):
    L *= i
    H *= n + 2 - i
    c[i] = L
    d[i] = H

e = [0 for _ in range(w + 1)]
temp = 1
for i in range(1, w + 1):
    temp *= w + 1 - i
    e[i] = temp


def ncmb(k):
    return d[k] // c[k]

def wcmb(k):
    if k > w or k <= 0:
        return 0
    elif k == w:
        return 1
    else:
        return e[k] // c[k]

print(n)
for k in range(2, n + 2):
    ans = ncmb(k) - wcmb(k-1)
    print(ans % MOD)

Submission status: Runtime Error

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

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

p = []
for i in range(n):
    if a[i] == d:
        p.append(i)

w = p[0] + n - p[1]

c = [0 for _ in range(n + 2)]

temp = 1
for i in range(1, n + 2):
    temp *= i
    c[i] = temp

def cmb(x, y):
    if y < 0 or y > x:
        return 0
    elif x == y:
        return 1
    else:
        return c[x] // c[y] // c[x - y] % MOD


print(n)
for k in range(2, n + 2):
    ans = cmb(n + 1, k) - cmb(w, k - 1)
    print(ans % MOD)

Submission status: Runtime Error

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

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

p = []
for i in range(n):
    if a[i] == d:
        p.append(i)

w = p[0] + n - p[1]

c = [0 for _ in range(n + 2)]

temp = 1
for i in range(1, n + 2):
    temp *= i
    c[i] = temp

def cmb(x, y):
    if x == y:
        return 1
    else:
        return c[x] // c[y] // c[x - y]


print(n)
for k in range(2, n + 2):
    if w >= k - 1:
        ans = cmb(n + 1, k) - cmb(w, k - 1)
    else:
        ans = cmb(n + 1, k)
    print(ans % MOD)

Submission status: Runtime Error

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

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

p = []
for i in range(n):
    if a[i] == d:
        p.append(i)

x = p[0]
y = p[1] - p[0] - 1
z = n - p[1]
w = x + z

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

print(n)
for k in range(2, n + 2):
    if w >= k - 1:
        ans = cmb(n + 1, k) - cmb(w, k - 1)
    else:
        ans = cmb(n + 1, k)
    print(ans % MOD)

Submission status: Runtime Error

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

MOD = 10 ** 9 + 7

b = sorted(a)

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

p = []
for i in range(n):
    if a[i] == d:
        p.append(i)

x = p[0]
y = p[1] - p[0] - 1
z = n - p[1]
w = x + z

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

print(n)
for k in range(2, n + 2):
    if w >= k - 1:
        ans = cmb(n + 1, k) - cmb(w, k - 1)
    else:
        ans = cmb(n + 1, k)
    print(ans % MOD)

Submission status: Runtime Error

Solution code:
import collections

def comb(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 = 1e9 + 7
n = int(input())
a = list(map(int,input().split()))
c = collections.Counter(a)
two = 0
for i in c:
    if c[i] == 2:
        two = i
before = 0
later = 0
temp = 0
for i in range(n+1):
    if temp == 2:
        later += 1
    if a[i] == two:
        temp += 1
    if temp == 0:
        before += 1

big = max(before,later)
small = before+later - big
for k in range(1,n+2):
    if big + small >= k-1:
        ans = comb(n+1,k) - comb(small+big,k-1)
        print(int(ans%mod))
    else:
        ans = comb(n+1,k)
        print(int(ans%mod))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(100001)
MOD = 1000000007

n = int(input())
alst = list(map(int, input().split()))
dic = defaultdict(list)
for i in range(n + 1):
    dic[alst[i]].append(i)

for v in dic.values():
    if len(v) == 2:
        left, right = v
        break

factMem = {}
def fact(x):
    if x <= 0:return 1
    if x in factMem:return factMem[x]
    factMem[x] = x * fact(x - 1) % MOD
    return factMem[x]

inverseMem = {}
def inverse(x):
    if x in inverseMem:return inverseMem[x]
    inverseMem[x] = pow(x, MOD - 2, MOD)
    return inverseMem[x]

def comb(x, y):
    if x < y:return 0
    return (fact(x) * inverse(fact(y)) * inverse(fact(x - y))) % MOD

for i in range(n + 1):
    print(comb(n + 1, i + 1) - comb(n - right + left, i))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

MOD = 1000000007

n = int(input())
alst = list(map(int, input().split()))
dic = defaultdict(list)
for i in range(n + 1):
    dic[alst[i]].append(i)

for v in dic.values():
    if len(v) == 2:
        left, right = v
        break

factMem = {}
def fact(x):
    if x <= 0:return 1
    if x in factMem:return factMem[x]
    factMem[x] = x * fact(x - 1) % MOD
    return factMem[x]

inverseMem = {}
def inverse(x):
    if x in inverseMem:return inverseMem[x]
    inverseMem[x] = pow(x, MOD - 2, MOD)
    return inverseMem[x]

def comb(x, y):
    if x < y:return 0
    return (fact(x) * inverse(fact(y)) * inverse(fact(x - y))) % MOD

for i in range(n + 1):
    print(comb(n + 1, i + 1) - comb(n - right + left, i))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

MOD = 1000000007

n = int(input())
alst = list(map(int, input().split()))
dic = defaultdict(list)
for i in range(n + 1):
    dic[alst[i]].append(i)

for v in dic.values():
    if len(v) == 2:
        left, right = v
        break

factMem = {}
def fact(x):
    if x <= 0:return 1
    if x in factMem:return factMem[x]
    factMem[x] = x * fact(x - 1)
    return factMem[x]

inverseMem = {}
def inverse(x):
    if x in inverseMem:return inverseMem[x]
    inverseMem[x] = pow(x, MOD - 2, MOD)
    return inverseMem[x]

def comb(x, y):
    if x < y:return 0
    return (fact(x) * inverse(fact(y)) * inverse(fact(x - y))) % MOD

for i in range(n + 1):
    print(comb(n + 1, i + 1) - comb(n - right + left, i))

Submission status: Runtime Error

Solution code:
#066-D
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
d=Counter(a).most_common(1)[0][0]
f,s=-1,-1
fc=[1 for i in range(n+2)]
for i in range(n+1):
    if a[i]==d:
        if f==-1:
            f=i
        else:
            s=i
    fc[i+1]=(i+1)*fc[i]
fc[n+1]=(n+1)*fc[n]
for k in range(1,n+2):
    if k==1:
        print(n)
    elif k>f+1+n+1-s-1:
        print(int((fc[n+1]/(fc[k]*fc[n+1-k]))%(pow(10,9)+7)))
    else:
        print(int(fc[n+1]/(fc[k]*fc[n+1-k])-fc[f+n-s]/(fc[k-1]*fc[f+n-s-(k-1)])%(pow(10,9)+7)))

Submission status: Runtime Error

Solution code:
#066-D
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
d=Counter(a).most_common(1)[0][0]
f,s=-1,-1
fc=[1 for i in range(n+2)]
for i in range(n+1):
    if a[i]==d:
        if f==-1:
            f=i
        else:
            s=i
    fc[i+1]=(i+1)*fc[i]
fc[n+1]=(n+1)*fc[n]
for k in range(1,n+2):
    if k==1:
        print(n)
    elif k>f+1+n+1-s-1:
        print(int(fc[n+1]/(fc[k]*fc[n+1-k])))
    else:
        print(int(fc[n+1]/(fc[k]*fc[n+1-k])-fc[f+n-s]/(fc[k-1]*fc[f+n-s-(k-1)])))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

class comb_calclator():
    def __init__(self, N, p):
        self.N = N
        self.p = p
        self.frac_N = [0 for i in range(N + 1)]
        self.frac_N[0] = 1L
        self.comb_N = {}
        for i in range(1, N + 1):
            self.frac_N[i] = (self.frac_N[i - 1] * i ) % p

    def comb(self, n, r):
        if n<0 or r<0 or n<r: return 0
        if n==0 or r==0: return 1
        if (n, r) in self.comb_N:
            return self.comb_N[(n, r)]
        a = self.frac_N[n]
        b = self.frac_N[r]
        c = self.frac_N[n - r]
        self.comb_N[(n, r)] = (a*power_func(b,self.p-2,self.p)*power_func(c,self.p-2, self.p))% self.p
        self.comb_N[(n, n - r)] = self.comb_N[(n, r)]
        return self.comb_N[(n, r)]

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [n] = [int(input_raw[0])]
    input_raw = read_func().strip().split()
    A = []
    N = n + 1
    for i in range(N):
        A.append(int(input_raw[i]))
    idx_dic = {}
    second_idx = 0
    first_idx = 0
    twice_a = 0
    for i in range(N):
        if A[i] not in idx_dic:
            idx_dic[A[i]] = [i]
        else:
            first_idx = idx_dic[A[i]]
            second_idx = i
            break

    cc = comb_calclator(N, 1000000007)

    sub_N = N - second_idx + first_idx

    for k in range(1, N + 1):
        sub1 = 0
        if k <= sub_N:
            sub1 = cc.comb(sub_N - 1, k - 1)  
        print (cc.comb(N, k) - sub1) % 1000000007

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]
mod = 10**9+7

memo=[0]*(N+2)
def comb(x, y):
    if x == N-1 and dp[y] > 0:
        return memo[y]
    elif y > x:
        return 0
    elif y * 2 > x:
        y = x - y
    result = 1
    for j in range(1, y + 1):
        result *= (x + j - y) * pow(j, mod - 2, mod)
        result %= mod
    if x == N-1:
        memo[y] = result
    return result


dupl = sum(A)-N*(N+1)//2
ds = []
for _ in range(N+1):
    if A[_] == dupl:
        ds += [_]
i, j = ds

print(N)
for k in range(2, N+2):
    print((comb(N-1, k)+comb(N-1, k-2)+2*comb(N-1, k-1)-comb(N-j+i, k-1)) % mod)