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:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

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)

N = 10**9+7
R = 10**5
modfact = [0]*(R+1)
def modfact_memo(n,N):
    r = 1
    modfact[0] = 1
    for i in range(1,n+1):
        r = r % N * i % N
        modfact[i] = r
modfact_memo(10**5,N)

# ax ≡ 1 (mod m)
modinv=[0]*(R+1)
def modinv_memo(a,m):
    for i in range(a+1):
        j = modfact[i]
        (inv, q, gcd_val) = egcd(j, m)
        modinv[i] = inv % m
modinv_memo(R,N)

def modconb(n,r,N):
    p = modfact[n]
    q1 = modinv[r]
    q2 = modinv[n-r]
    return p*q1%N*q2%N


n = int(input())
a = list(map(int,input().split()))
b=[0]*n
for i in range(n+1):
    b[a[i]-1] += 1
w = b.index(2)+1
index = []
for i in range(n+1):
    if a[i] == w:
        index.append(i)
l = index[0]
r = n - index[1]

for i in range(n+1):
    ans = modconb(n+1,i+1,N)
    if l+r >= i:
        ans -= modconb(l+r,i,N)
        ans %= N
    print(ans)

Submission status: Runtime Error

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

p = 10**9 + 7

found = {}
for i, a in enumerate(A):
    if a in found:
        dup = a
        dup_1 = found[a]
        dup_2 = i
    found[a] = i

from functools import lru_cache

@lru_cache(maxsize=None)
def gfp_inv(x, p):
    return pow(x, p - 2, p)

from itertools import chain, accumulate
memo_fact = list(chain([1], accumulate(range(1, 10**5 + 1), lambda a, x: a * x % p)))

def comb(n, m):
    if m < 0 or n < m: return 0
    if n == m: return 1
    return memo_fact[n] * gfp_inv(memo_fact[n - m], p) * gfp_inv(memo_fact[m], p) % p

intv = dup_2 - dup_1 - 1
for k in range(1, n + 2):
    ans = comb(n + 1, k)
    ans -= comb(n + 1 - intv - 2, k - 1)
    print(ans % p)

Submission status: Runtime Error

Solution code:
init_input()

n = int(input())
A = [int(x) for x in input().split()]

found = {}
for i, a in enumerate(A):
    if a in found:
        dup = a
        dup_1 = found[a]
        dup_2 = i
    found[a] = i

from functools import lru_cache

@lru_cache(maxsize=None)
def gfp_inv(x, p):
    return pow(x, p - 2, p)

@lru_cache(maxsize=None)
def fact(n, m, p):
    ret = 1
    for i in range(m, n + 1):
        ret = (ret * i) % p
    return ret

def comb(n, m):
    if m < 0 or n < m: return 0
    if n == m: return 1
    return fact(n, n - m + 1, p) * gfp_inv(fact(m, 1, p), p) % p

p = 10**9 + 7

intv = dup_2 - dup_1 - 1
for k in range(1, n + 2):
    ans = comb(n + 1, k)
    ans -= comb(n + 1 - intv - 2, k - 1)
    print(ans % p)

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
facts = [1]
for i in range(1, 10**5+1):
    facts.append((i*facts[i-1])%MOD)
def nCk(n, k):
    if n < k or n == 0: return 0
    return (facts[n]*pow(facts[k], MOD-2, MOD)%MOD * pow(facts[n-k], MOD-2, MOD))%MOD

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

# Search doubling number and its indexes
indexes = [[] for _ in range(n+1)] # 0 to n:max(a)
for i in range(n+1):
    indexes[a[i]].append(i)
for idx in indexes:
    if len(idx) == 2: idxs = sorted(idx)

for k in range(1, n+1+1):
    p_all = nCk(n+1, k)
    p_double = nCk(n+1-(idxs[1]-idxs[0]+1), k-1)
    print((p_all-p_double)%MOD)

Submission status: Runtime Error

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

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


def Pascal(N):
	if N == 1:
		return [1]
	else:
		tb1 = [1,1]
		for i in range(2,N+1):
			tb2=[1]
			for j in range(1,i):
				tb2.append((tb1[j-1]+tb1[j])%mod)
			tb2.append(1)
			tb1 = tb2[:]
		return tb1

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


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

Submission status: Runtime Error

Solution code:
import math

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

n = int(input())

a = list(map(int, input().split()))


for x in set(a):
    if a.count(x) > 1:
        num=x

flag=0

for i in range(n):
    if a[i]==num:
        if flag==0:
            th1=i
            flag=1
        else:
            th2=i

print(n)
print(comb(n+1, 2) - th1+th2-n)

for k in range(3, n+2):
    if n-th2+th1<k-1:
        print(comb(n+1, k)%1000000007)
    else:
        print((comb(n+1, k)-comb(n-th2+th1, k-1))%(1000000007))

Submission status: Runtime Error

Solution code:
MOD = 10**9+7

def mod_pow(x, n):
  if x==0: return 1
  res = 1
  while n > 0:
    if n&1:
      res = (res*x)%MOD
    x = (x*x)%MOD
    n >>= 1
  return res

fact, invfact = [0]*(10**5+1), [0]*(10**5+1)
fact[0], invfact[0] = 1, 1
for i in range(1, 10**5+1):
  fact[i] = (fact[i-1]*i)%MOD
  invfact[i] = mod_pow(fact[i], MOD-2)%MOD

def comb(n, r):
  if n<r or n==0 or r==0: return 0
  return (((fact[n]*invfact[r])%MOD)*invfact[n-r])%MOD

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
for i, ele in enumerate(a):
  if d[ele] == 0:
    d[ele]= i+1
  else:
    l = d[ele]
    r = i+1

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

Submission status: Runtime Error

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

Solution code:
import math

def nCr(n,r):
    if n < r:
        return 0
    f = math.factorial
    return f(n) / f(r) / f(n-r)

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

MOD = 10**9+7

d = sum(a)-n*(n+1)//2
x = a.index(d)
y = a[x+1:].index(d)+x+1

for i in range(1, n+2):
    print(int(nCr(n+1, i) - nCr((n+x-y), (i-1)))%MOD)

Submission status: Runtime Error

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

mod=10**9+7
 
#階乗計算
factorial=[1]
inverse=[1]
for i in range(1,N+2):
    factorial.append(factorial[-1]*i %mod)
    inverse.append((pow(factorial[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

print(N)
for i in range(2,N+2):
    print(int(nCr(N+1,i)-nCr(l+N-r,i-1))%mod)

Submission status: Runtime Error

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 if se[0] + N -se[1] >= i:
      ans-=nCr(se[0]+N-se[1],i)
      print(int(ans))

Submission status: Runtime Error

Solution code:

MODULO = 10**9 + 7
def modulo(x):
    return x % MODULO

n = int(input())
xs = list(map(int, input().split()))

def locate_dup(xs):
    d = {}
    for i,x in enumerate(xs):
        if x in d:
            return d[x], i
        else:
            d[x] = i
    assert(False)

first, second = locate_dup(xs)


class X:
    def __init__(self, first, second, length):
        self.dup_first = first
        self.dup_second = second
        self.length = length
        self.memo = {}

    def C(self, k, pos):
        v = self.memo.get((k, pos), None)
        if v is None:
            v = self.calcC(k, pos)
            self.memo[(k, pos)] = v
        return v


    def calcC(self, k, pos):
        if k <= 0 or pos >= self.length:
            return 0
        elif k == 1:
            if pos <= self.dup_first:
                return modulo(self.length - pos - 1)
            else:
                return modulo(self.length - pos)
        else:
            if pos == self.dup_first:
                return modulo(self.C(k-1, pos+1) + self.C(k, pos+1) - self.C(k-1, self.dup_second + 1))
            else:
                return modulo(self.C(k-1, pos+1) + self.C(k, pos+1))

x = X(first, second, n+1)

for i in range(0, n+1):
    print(x.C(i+1, 0))

Submission status: Runtime Error

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 = ls.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: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = set()
dup = list(set([x for x in a if x in s or s.add(x)]))[0]

start = a.index(dup)
end = a.index(dup, start+1)
d = end - start

def comb(n, r):
    if(r==0):
        return 1
    ret = n
    for i in range(1, r):
        ret = ret * (n-i) / (i+1)
    return int(ret)

for i in range(n+1):
    if(i == 0):
        print(n)
        continue
    c = comb(n+1, min(i+1, n-i))
    ans = c - max(0, comb(n-d, i))
    print(ans%1000000007)

Submission status: Runtime Error

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

from collections import Counter
import re

def pow(a, x):
        y = 1
        p = a
        n = x % mask
        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)

'''
for i in range(0, n + 1):
        x = a.index(a[i])
        if a[i] in a[x+1:]:
                left = i
                right = a[x+1:].index(a[i]) + x + 1
                break
'''

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):
                ans -= (com[left + n - right] * inv[i - 1] * inv[left + n - right - i + 1]) % mask
        print (ans - x)

Submission status: Runtime Error

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

import re

n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0
mask = 10**9 + 7

com = [0]*(n+2)

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

for i in range(0, n + 1):
        x = a.index(a[i])
        if a[i] in a[x+1:]:
                left = i  
                right = a[x+1:].index(a[i]) + x + 1
                break

for i in range(1, n + 2):
        ans = (com[n + 1] / (com[i] * com[n + 1 - i]))
        x = (com[left + n - right] / (com[i - 1] * com[left + n - right - i + 1]))
        print (ans - x) % mask

Submission status: Runtime Error

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

import re

n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0
mask = 10**9 + 7

com = [0]*n+2

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

for i in range(0, n + 1):
        x = a.index(a[i])
        if a[i] in a[x+1:]:
                left = i  
                right = a[x+1:].index(a[i]) + x + 1
                break

for i in range(1, n + 2):
        ans = (com[n + 1] / (com[i] * com[n + 1 - i]))
        x = (com[left + n - right] / (com[i - 1] * com[left + n - right - i + 1]))
        print (ans - x) % mask

Submission status: Runtime Error

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

import re

n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0
mask = 10**9 + 7

pow = [0]*n+2

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

for i in range(0, n + 1):
        x = a.index(a[i])
        if a[i] in a[x+1:]:
                left = i
                right = a[x+1:].index(a[i]) + x + 1
                break

for i in range(1, n + 2):
        ans = (pow[n + 1] / (pow[i] * pow[n + 1 - i]))
        x = (pow[left + n - right] / (pow[i - 1] * pow[left + n - right - i + 1]))
        print (ans - x) % mask

Submission status: Runtime Error

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

import re



n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0
mask = 10**9 + 7

pow = [0]*n+2

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

for i in range(0, n + 1):
        x = a.index(a[i])
        if a[i] in a[x+1:]:
                left = i
                right = a[x+1:].index(a[i]) + x + 1
                break

for i in range(1, n + 2):
        ans = (pow[n + 1] / (pow[i] * pow[n + 1 - i]))
        x = (pow[left + n - right] / (pow[i - 1] * pow[left + n - right - i + 1]))
        print (ans - x) % mask

Submission status: Runtime Error

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

import re

def comb(n, k):
        a = [0] * 17
        if (n - k < k):
                k = n - k
        if (k == 0):
                return 1
        if (k == 1):
                return n
        if (k > 17):
                return 0
        for i in range(1, k):
                a[i] = i + 2
        for i in range(3, (n - k + 2)):
                a[0] = i
                for j in range(1, k):
                        a[j] += a[j - 1]
        return a[k - 1]

n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0
mask = 10**9 + 7

for i in range(0, n + 1):
        x = a.index(a[i])
        if a[i] in a[x+1:]:
                left = i
                right = a[x+1:].index(a[i]) + x + 1
                break

for i in range(1, n + 2):
        ans = comb(n + 1, i)
        ans -= comb(left + n - right, i - 1)
        print ans % mask

Submission status: Runtime Error

Solution code:
import math

def nCm(n, m):
    return math.factorial(n) // (math.factorial(m) * (math.factorial(n - m)))


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

saw = [-1] * n
left = 0
right = 0
for i in range(n):
    if saw[a[i] - 1] == -1:
        saw[a[i] - 1] = i
    else:
        left, right = saw[a[i] -1], n - i
        break
print(left, right)

for i in range(1, n+2):
    if i == 1:
        print(n)
    else:
        print((nCm(n+1, i) - nCm(left+right, i - 1) % 1000000007))

Submission status: Runtime Error

Solution code:
import math

def nCm(n, m):
    return fact(n) // (fact(m) * (fact(n - m)))


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

saw = [-1] * n
left = 0
right = 0
for i in range(n):
    if saw[a[i] - 1] == -1:
        saw[a[i] - 1] = i
    else:
        left, right = saw[a[i] -1], n - i
        break
print(left, right)

for i in range(1, n+2):
    if i == 1:
        print(n)
    else:
        print((nCm(n+1, i) - nCm(left+right, i - 1) % 1000000007))

Submission status: Runtime Error

Solution code:
import math

def nCm(n, m):
    return fact(n) // (fact(m) * (fact(n - m)))


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

saw = [-1] * n
left = 0
right = 0
for i in range(n):
    if saw[a[i] - 1] == -1:
        saw[a[i] - 1] = i
    else:
        left, right = saw[a[i] -1], n - i
        break
print(left, right)

for i in range(1, n+2):
    if i == 1:
        print(n)
    else:
        print((nCm(n+1, i) - nCm(left+right, i - 1) % 1000000007)

Submission status: Runtime Error

Solution code:
b=10**9+7
num = [-1]*(n+1)
temp=1
temp2=1
for i in range(len(a)):
        if num[a[i]] != -1:
                p1,p2=num[a[i]],i
        num[a[i]]=i
for k in range(1,len(a)+1):
        if k == 1:
                print(n)
        
        elif k == len(a):
                print(1)
        else:
                for l in range(k):
                        temp=temp*(n+1-l)/(k-l)
                        if k-l-1 > 0:
                                temp2=temp2*(n-p2+p1-l)/(k-l-1)
                print(int((temp-temp2)%b))
                temp = 1
                temp2 =1

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=10**9+7
num = [-1]*(n+1)
temp=1
temp2=1
for i in range(len(a)):
        if num[a[i]] != -1:
                p1,p2=num[a[i]],i
        num[a[i]]=i
for k in range(1,len(a)+1):
        if k == 1:
                print(n)
        else:
                for l in range(k):
                        temp=temp*(n+1-l)/(k-l)
                        if k-l-1 != 0:
                                temp2=temp2*(n-p2+p1-l)/(k-l-1)
                print(int((temp-temp2)%b))
                temp = 1        
                temp2 =1

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Here your code !

l=int(input())+1
if l==2:
    print(1)
    print(1)
    exit()
mod = 10**9+7
N = 10**5+2
g1 = [1, 1]  #0! と1!
g2 = [1, 1]  #(0!)^-1 と(1!)^-1
inverse = [0, 1]
data=list(map(int,input().split()))
for i in data:
    if data.count(i)==2:
        x=i
        break
for i in range( 2, N + 1 ):
    #元テーブルは，最後尾の要素にiを乗算したのを加える
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    #逆元テーブルは，最後尾の要素にinverseの最後尾を乗算したのを加える
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
def combination(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
 
c1=[1 for i in range(10005)]
l-=1
for i in range(1,l+2):
    c1[i]=combination(l+1,i,mod)
t2=data.index(x)
t1=data.index(x,t2-1)
for i in range(1,l+2):
    print(c1[i]-combination(t2+l-t1,i-1,mod))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Here your code !

l=int(input())+1
if l==2:
    print(1)
    print(1)
    exit()
mod = 10**9+7
N = 10**5+2
g1 = [1, 1]  #0! と1!
g2 = [1, 1]  #(0!)^-1 と(1!)^-1
inverse = [0, 1]
data=list(map(int,input().split()))
for i in data:
    if data.count(i)==2:
        x=i
        break
for i in range( 2, N + 1 ):
    #元テーブルは，最後尾の要素にiを乗算したのを加える
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    #逆元テーブルは，最後尾の要素にinverseの最後尾を乗算したのを加える
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
def combination(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
 
c1=[1 for i in range(10004)]
l-=1
for i in range(1,l+2):
    c1[i]=combination(l+1,i,mod)
t1=data.index(x,2)
t2=data.index(x)
for i in range(1,l+2):
    print(c1[i]-combination(t2+l-t1,i-1,mod))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Here your code !

l=int(input())+1
if l==2:
    print(1)
    print(1)
    exit()
mod = 10**9+7
N = 10**5+2
g1 = [1, 1]  #0! と1!
g2 = [1, 1]  #(0!)^-1 と(1!)^-1
inverse = [0, 1]
data=list(map(int,input().split()))
for i in data:
    if data.count(i)==2:
        x=i
        break
for i in range( 2, N + 1 ):
    #元テーブルは，最後尾の要素にiを乗算したのを加える
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    #逆元テーブルは，最後尾の要素にinverseの最後尾を乗算したのを加える
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
def combination(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
 
c1=[1 for i in range(10002)]
l-=1
for i in range(1,l+2):
    c1[i]=combination(l+1,i,mod)
t1=data.index(x,2)
t2=data.index(x)
for i in range(1,l+2):
    print(c1[i]-combination(t2+l-t1,i-1,mod))

Submission status: Runtime Error

Solution code:
l=int(input())+1
if l==2:
    print(1)
    print(1)
    exit()
mod = 10**9+7
N = 10**5+2
g1 = [1, 1]  #0! と1!
g2 = [1, 1]  #(0!)^-1 と(1!)^-1
inverse = [0, 1]
data=list(map(int,input().split()))
for i in data:
    if data.count(i)==2:
        x=i
        break
for i in range( 2, N + 1 ):
    #元テーブルは，最後尾の要素にiを乗算したのを加える
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    #逆元テーブルは，最後尾の要素にinverseの最後尾を乗算したのを加える
    g2.append( (g2[-1] * inverse[-1]) % mod )

def combination(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

c1=[1]
l-=1
for i in range(1,l+2):
    c1.append(combination(l+1,i,mod))
t1=data.index(x,2)
t2=data.index(x)
for i in range(1,l+2):
    print(c1[i]-combination(l+1-t1))

Submission status: Runtime Error

Solution code:
def combi(a,b):
    if b < 0:
        return 0
    if b > a - b:
        b = a - b
    if b == 0:
        return 1
    else:
        return combi(a-1,b-1)*a/b

n = int(raw_input())
l = map(int, raw_input().split())
ct = [0 for _ in range(n+1)]
for i in l:
    ct[i] += 1
for i,c in enumerate(ct):
    if c == 2:
        d = i
        break
s = l.index(d)
l.reverse()
s += l.index(d)
print n
for i in range(2, n+2):
    print (combi(n+1, i) - combi(s, i-1)) % (10**9 + 7)

Submission status: Runtime Error

Solution code:
from scipy.misc import comb

n = int(input())
a = list(map(int, input().split()))
appeared = {}
double = [0, 0]

for i, v in enumerate(a):
    if v in appeared:
        double = [appeared[v], i]
        break
    else:
        appeared[v] = i

duplicateElemSize = double[0] + n - double[1]
for i, v in enumerate(a):
    combinations = comb(n+1, i+1) - comb(duplicateElemSize, i)
    print(int(combinations % (10**9 + 7)))

Submission status: Runtime Error

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

def calc_index(a):
    t = sorted(a)
    for i, x in enumerate(t[1:]):
        if t[i] == x:
            break
    result = []
    for i, v in enumerate(a):
        if v == x:
            result.append(i)
    return result

f, e = calc_index(a)
out = n - e + f

facts = [0 for x in range(10**5 + 1)]
fresult = 1
for i in range(1, 10**5 + 1):
    fresult *= i
    if fresult > M:
        fresult %= M
    facts[i] = fresult

def fact(a):
    return facts[a]

def powmod(a, b):
    if b == 0:
        return 1
    elif b & 1:
        return (powmod(a, b - 1) * a) % M
    else:
        return powmod(a, b // 2)**2 % M

def c(a, b):
    if b > a: return 0
    return fact(a) * powmod(fact(b) * fact(a - b) % M, M - 2) % M

print(n)
for i in range(2, n + 1):
    c1, c2 = c(n + 1, i), c(out, i - 1)
    r = c1 - c2
    if r < 0:
        r += M
    print(r%M)
print(1)

Submission status: Runtime Error

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

def calc_index(a):
    t = sorted(a)
    for i, x in enumerate(t[1:]):
        if t[i] == x:
            break
    result = []
    for i, v in enumerate(a):
        if v == x:
            result.append(i)
    return result

f, e = calc_index(a)
out = n - e + f

facts = [0 for x in range(10**5 + 1)]
fresult = 1
for i in range(1, 10**5 + 1):
    fresult *= i
    if fresult > M:
        fresult %= M
    facts[i] = fresult

def fact(a):
    return facts[a]

def powmod(a, b):
    if b == 0:
        return 1
    elif b & 1:
        return (powmod(a, b - 1) * a) % M
    else:
        return powmod(a, b // 2)**2 % M

def c(a, b):
    if b > a: return 0
    return fact(a) * powmod(fact(b) * fact(a - b) % M, M - 2) % M

for i in range(1, n + 1):
    c1, c2 = c(n + 1, i), c(out, i - 1)
    r = c1 - c2
    if r < 0:
        r += M
    print(r)
print(1)

Submission status: Runtime Error

Solution code:
def c(a,b):
    if b==0:
        return 0
    elif a==b:
        return 1
    s=1.0
    if a-b>=b:
        for i in range(b):
            s*=a-i
            s/=b-i
    else:
        s=c(a,a-b)

    return int(s)

n=int(raw_input())
a=map(int,raw_input().split(' '))

if a.index(a[-1])!=len(a)-1:
    indexes=[a.index(a[-1]),len(a)-1]
else:
    sa=sorted(set(a), key=a.index)
    for i in range(len(a)-1):
        if a[i]!=sa[i]:
            t=i
            break
    
    indexes = [i for i, x in enumerate(a) if x==a[t]]
d1=indexes[0]
d2=len(a)-1-indexes[1]


r=[0]*(n+1)
for k in range(1,(n+1)/2+1):
    if k==1:
        r[0]=n
        if len(r)>2:
            r[-2]=n+1
    else:
        s=c(n+1,k) #(n+1)C_k
        r[n+1-k-1]=s%(10**9+7)   
        if (d1+d2)+1>=k:
            s-=c(d1+d2,k-1)
        r[k-1]=s%(10**9+7)   
        
r[-1]=1

for x in r:
    print x

Submission status: Runtime Error

Solution code:
def c(a,b):
    if b==0:
        return 0
    elif a==b:
        return 1
    s=1.0
    if a-b>=b:
        for i in range(b):
            s*=a-i
            s/=b-i
    else:
        s=c(a,a-b)

    return int(s)

n=int(raw_input())
a=map(int,raw_input().split(' '))

if a.index(a[-1])!=len(a)-1:
    indexes=[len(a)-2,len(a)-1]
else:
    sa=sorted(set(a), key=a.index)
    for i in range(len(a)-1):
        if a[i]!=sa[i]:
            t=i
            break
    
    indexes = [i for i, x in enumerate(a) if x==a[t]]
d1=indexes[0]
d2=len(a)-1-indexes[1]


r=[0]*(n+1)
for k in range(1,(n+1)/2+1):
    if k==1:
        r[0]=n
        if len(r)>2:
            r[-2]=n+1
    else:
        s=c(n+1,k) #(n+1)C_k
        r[n+1-k-1]=s%(10**9+7)   
        if (d1+d2)+1>=k:
            s-=c(d1+d2,k-1)
        r[k-1]=s%(10**9+7)   
        
r[-1]=1

for x in r:
    print x

Submission status: Runtime Error

Solution code:
def c(a,b):
    if b==0:
        return 0
    elif a==b:
        return 1
    s=1.0
    if a-b>=b:
        for i in range(b):
            s*=a-i
            s/=b-i
    else:
        s=c(a,a-b)

    return int(s)

n=int(raw_input())
a=map(int,raw_input().split(' '))

if a[-2]==a[-1]:
    indexes=[len(a)-2,len(a)-1]
else:
    sa=sorted(set(a), key=a.index)
    for i in range(len(a)-1):
        if a[i]!=sa[i]:
            t=i
            break
    
    indexes = [i for i, x in enumerate(a) if x==a[t]]
d1=indexes[0]
d2=len(a)-1-indexes[1]


r=[0]*(n+1)
for k in range(1,(n+1)/2+1):
    if k==1:
        r[0]=n
        if len(r)>2:
            r[-2]=n+1
    else:
        s=c(n+1,k) #(n+1)C_k
        r[n+1-k-1]=s%(10**9+7)   
        if (d1+d2)+1>=k:
            s-=c(d1+d2,k-1)
        r[k-1]=s%(10**9+7)   
        
r[-1]=1

for x in r:
    print x

Submission status: Runtime Error

Solution code:
import sys
import math

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

def combination(n,k):
	if k == 0:
		return 1
	elif k == n:
		return 1
	else:
		return 2

indexes = [i for i, x in enumerate(a_array) if x == 1]
r = indexes[0] + N-indexes[1]

for i in range(1,N+2):
	if r >= i-1:
		print(int(combination(N+1,i)-combination(r,i-1)))
	else:
		print(int(combination(N+1,i)))

Submission status: Runtime Error

Solution code:
import sys
import math

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

def combination(n,k):
	if k == 0:
		return 1
	elif k == n:
		return 1
	else:
		return math.factorial(n)/math.factorial(n-k)/math.factorial(k)

indexes = [i for i, x in enumerate(a_array) if x == 1]
r = indexes[0] + N-indexes[1]

for i in range(1,N+2):
	if r >= i-1:
		print(int(combination(N+1,i)-combination(r,i-1)))
	else:
		print(int(combination(N+1,i)))

Submission status: Runtime Error

Solution code:
import sys
#import math

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

def combination(n,k):
	if k == 0:
		return 1
	elif k == n:
		return 1
	else:
		return math.factorial(n)/math.factorial(n-k)/math.factorial(k)

#hoge = "1 2 1 3"
#a_array = list(map(int,hoge.split(" ")))
#a_array = [2,3,1,4,5,1,6,7]
#a_array = [1,2,1,3]
#N = len(a_array)-1

#print(N)
#print(a_array)

indexes = [i for i, x in enumerate(a_array) if x == 1]
#print(indexes)
r = indexes[0] + N-indexes[1]
#print(r)

for i in range(1,N+2):
	if r >= i-1:
		print(int(combination(N+1,i)-combination(r,i-1)))
	else:
		print(int(combination(N+1,i)))