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

Solution code:
MOD = 10**9 + 7

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)

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())
L = n+1
inv = [None]*(n+2)

for i,a in enumerate(map(int,input().split())):
  if inv[a-1] is None:
    inv[a-1] = i
  else:
    m = n - i + inv[a-1]
    break


b = 1
for i in range(2,m+1):
  b *= i
  b %= MOD

a = b
for i in range(m+1, L+1):
  a *= i
  a %= MOD

ik = modinv(a,MOD)

for i in reversed(range(L+1)):
  inv[i] = ik
  ik *= i
  ik %= MOD

r1 = [(a*inv[k]*inv[L-k])%MOD for k in range(L//2+1)]
r2 = [(b*inv[k]*inv[m-k])%MOD for k in range(m//2+1)]



# C(n+1,k) - C(m,k-1)
# C(n,k) = n!/(k!(n-k)!)

for k in range(1, m+2):
  print((r1[min(k,L-k)]-r2[min(k-1,m-k+1)])%MOD)

for k in range(m+2,n+2):
  print(r1[min(k,L-k)]%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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)

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())
temp = [None]*(n+2)

for i,a in enumerate(map(int,input().split())):
  if temp[a-1] is None:
    temp[a-1] = i
  else:
    m = n - i + temp[a-1]
    break


b = 1
for i in range(2,m+1):
  b *= i
  b %= MOD

a = b
for i in range(m+1, n+2):
  a *= i
  a %= MOD

ik = modinv(a,MOD)

for i in reversed(range(n+2)):
  temp[i] = ik
  ik *= i
  ik %= MOD


# C(n+1,k) - C(m,k-1)
# C(n,k) = n!/(k!(n-k)!)

for k in range(1, m+2):
  s = a*temp[k]*temp[n+1-k]
  t = b*temp[k-1]*temp[m+1-k]
  print((s-t)%MOD)

for k in range(m+2,n+2):
  s = a*temp[k]*temp[n+1-k]
  print(s%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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)

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())
temp = [None]*n

for i,a in enumerate(map(int,input().split())):
  if temp[a-1] is None:
    temp[a-1] = i
  else:
    m = n - i + temp[a-1]
    break

s = n + 1
t = 1
print(n)

ik = 1
for k in range(n):
  t *= (m-k)*ik
  t %= MOD
  ik = modinv(k+2, MOD)
  s *= (n-k)*ik
  s %= MOD
  print((s-t)%MOD)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def M(n): return ModInt(n)
def MI(): return M(I())

class ModInt():
    def __init__(self, n):
        self.n = n

    def __add__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n+x) % mod)

    def __sub__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n-x) % mod)

    def __mul__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n*x) % mod)

    def __truediv__(self, x):
        x = ModInt.xn(x)
        return ModInt(self.n * pow(x, mod-2, mod) % mod)

    @classmethod
    def xn(cls, x):
        if isinstance(x, ModInt):
            return x.n
        return x

    def __str__(self):
        return str(self.n)

def main():
    n = I()
    a = LI_()
    b = [-1] * n
    t = 1
    for i in range(n+1):
        c = a[i]
        if b[c] >= 0:
            t = i - b[c]
            break
        b[c] = i

    rr = [n]
    nb = M(n+1)
    nt = M(1)
    for i in range(2,n+2):
        nb *= n-i+2
        nb /= i

        tr = nb.n
        if n-t >= i-1:
            nt *= n-t-i+2
            nt /= i-1
            tr -= nt.n
            tr %= mod
        rr.append(tr)
    return '\n'.join(map(str, rr))

print(main())

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
occur = [0 for i in range(n + 1)]
MOD = 1000000007
for i in range(n + 1):
    if occur[a[i]] > 0: val = n - 1 - i + occur[a[i]]
    else: occur[a[i]] = i + 1
inv = [0 if i > 2 else 1 for i in range(n + 2)]
pinv = [0 if i > 2 else 1 for i in range(n + 2)]
perm = [0 if i > 2 else 1 for i in range(n + 2)]
for i in range(2, n + 2):
    inv[i] = -int(MOD / i) * inv[MOD % i] + MOD
    pinv[i] = pinv[i - 1] * inv[i] % MOD
    perm[i] = perm[i - 1] * i % MOD
def C(n, m):
    return (perm[m] * pinv[n] % MOD) * pinv[m - n] % MOD if n <= m else 0
for i in range(1, n + 2):
    temp = C(i, n + 1) - C(i - 1, val)
    if temp < 0: temp += MOD
    print(temp)

Submission status: Accepted

Solution code:
def ncr(n, r):
    return fact[n] * inv_fact[r] * inv_fact[n - r] % div


def find_duplicated(aa):
    appeared = [-1] * (n + 1)
    for i, a in enumerate(aa):
        if appeared[a] >= 0:
            return appeared[a], i
        appeared[a] = i


div = int(1e9 + 7)
n = int(input())
aa = list(map(int, input().split()))

fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, n + 2):
    fact_tmp *= i
    fact_tmp %= div
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, div - 2, div))

i1, i2 = find_duplicated(aa)
outside_n = n + 1 - (i2 - i1 + 1)

for part_n in range(1, n + 2):
    sub = ncr(outside_n, part_n - 1) if outside_n >= part_n - 1 else 0
    print((ncr(n + 1, part_n) - sub) % div)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int,stdin.readline().split()))

MOD = 10**9+7

class Comb:
    def __init__(self, size):
        self.fact = [0 for i in range(size + 1)]
        self.inv_fact = [0 for i in range(size + 1)]
        self.factrical(size)

    def nCr(self, n,r):
        ret = self.fact[n]
        ret *= self.inv_fact[n-r]
        ret %= MOD
        ret *= self.inv_fact[r]
        ret %= MOD
        return ret

    def factrical(self, N):
        self.fact[0] = 1
        self.inv_fact[0] = 1
        for i in range(1,N+1):
            self.fact[i] = i * self.fact[i-1] % MOD
            self.inv_fact[i] = self.inv(self.fact[i]) % MOD

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

N = ni()
a = na()
c = [-1 for i in range (N)]
index = [-1,-1]

for i, x in enumerate(a):
    if (c[x-1]!=-1):
        index[0] = c[x-1]
        index[1] = i
        break

    c[x-1] = i

co = Comb(N+1)
for i in range(1, N+2):
    ans = co.nCr(N+1,i)
    if ((N-index[1]) + (index[0])>=i-1 ):
        ans -= co.nCr((N-index[1]) + (index[0]),i-1) 
        
    print (ans%MOD)

Submission status: Accepted

Solution code:
modulus = 10**9+7
p = modulus-2
n = int(input())
factorial = [1]
for i in range(1, n+2):
    factorial.append((factorial[-1] * i) % modulus)

factorial_inv = [pow(f, p, modulus) for f in factorial]

def nCr(n, r):
    return (factorial[n] * factorial_inv[r]) % modulus * factorial_inv[n-r] % modulus

xs = list(map(int, input().split()))
d = {}
s = set()
for i, x in enumerate(xs):
    if x in s:
        dup1 = d[x]
        dup2 = i
    else:
        s.add(x)
        d[x] = i

outer = n+1 - (dup2 - dup1 + 1)
print(n)
for k in range(2, outer+2):
    print((nCr(n+1, k) - nCr(outer, k-1))%modulus)
for k in range(outer+2, n+2):
    print(nCr(n+1, k))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
occur = [0 for i in range(n + 1)]
MOD = 1000000007
for i in range(n + 1):
    if occur[a[i]] > 0: val = n - 1 - i + occur[a[i]]
    else: occur[a[i]] = i + 1
inv = [0 if i > 2 else 1 for i in range(n + 2)]
pinv = [0 if i > 2 else 1 for i in range(n + 2)]
perm = [0 if i > 2 else 1 for i in range(n + 2)]
for i in range(2, n + 2):
    inv[i] = -int(MOD / i) * inv[MOD % i] + MOD
    pinv[i] = pinv[i - 1] * inv[i] % MOD
    perm[i] = perm[i - 1] * i % MOD
def C(n, m):
    return (perm[m] * pinv[n] % MOD) * pinv[m - n] % MOD if n <= m else 0
for i in range(1, n + 2):
    temp = C(i, n + 1) - C(i - 1, val)
    if temp < 0: temp += MOD
    print(temp)

Submission status: Accepted

Solution code:
f=[0 for _ in range(100001)]
mo= 1000000007
def ksm(a, b):
	ans=1
	while b:
		if (b&1):
		    ans=ans*a%mo
		b>>=1
		a=a*a%mo
	
	return ans

def main():
	n=int(input())
	l=list(map(int,input().split()))
	for i in range(1,n+2):
		x=l[i-1]
		if (f[x]):
		    l=f[x]-1;r=n-i+1;break
		else:
		    f[x]=i
	
	print(n)
	t=l+r
	sum1=1
	sum=n+1
	for i in range(2,n+2):
		if (t>=i-1):
		    sum1=(sum1*(t-i+2)%mo*ksm(i-1,mo-2))%mo
		else:
		    sum1=0
		sum=(sum*(n-i+2)%mo*ksm(i,mo-2))%mo
		print((sum-sum1+mo)%mo)
	
main()

Submission status: Accepted

Solution code:
n,*A=map(int,open(0).read().split());n+=1;f=[1]*-~n;r=f[:];M=10**9+7
for a in A:r[a]+=1
i=r.index(3);d=A.index;L=d(i);L+=n-d(i,L+1);*X,=range(1,n+1)
for i in X:f[i]=e=f[i-1]*i%M;r[i]=pow(e,M-2,M)
for k in X:print((f[n]*r[k]*r[n-k]-(k<=L)*(f[L-1]*r[k-1]*r[L-k]))%M)

Submission status: Accepted

Solution code:
n,*A=map(int,open(0).read().split())
f=[1]*(n+2);r=f[:]
MOD=10**9+7
for i in range(n+1):f[i+1]=e=f[i]*-~i%MOD;r[i+1]=pow(e,MOD-2,MOD)
B=[0]*(n+1)
for a in A:B[a]+=1
i=B.index(2)
L=A.index(i);R=A.index(i,L+1)
for k in range(1,n+2):
    print((f[n+1]*r[k]*r[n+1-k]-(k<=L+n+1-R and f[L-1+n+1-R]*r[k-1]*r[L+n+1-k-R]))%MOD)

Submission status: Accepted

Solution code:
def nCk(n,k,mod=10**9+7):
    if n<k or k<0 or n<0:return 0
    return fact[n]%mod * pow(fact[n-k]*fact[k],mod-2,mod) % mod

mod = 10**9+7
n=int(raw_input())
a=map(int,raw_input().split())
cnt=[0]*(n+1)
for i in xrange(n+1):
    cnt[a[i]]+=1
dnum=0
for i in xrange(n+1):
    if cnt[i]==2:
        dnum=i
        break
idx=[]
fact=[0]*(n+5)
fact[0]=1
for i in xrange(n+1):
    fact[i+1] = (i+1)*fact[i]%mod
for i in xrange(n+1):
    if dnum==a[i]:
        idx.append(i)

y=n-idx[1]
x=idx[0]

for i in xrange(n+1):
    #print nCk(y,i)
    print (nCk(n+1, i+1) - nCk(x+y,i)%mod)%mod

Submission status: Accepted

Solution code:
from math import factorial
def nCk(n,k,mod=10**9+7):
    if n<k or k<0 or n<0:return 0
    return fact[n]*inv[n-k]*inv[k] % mod

mod = 10**9+7
n=int(raw_input())
a=map(int,raw_input().split())
cnt=[0]*(n+1)
for i in xrange(n+1):
    cnt[a[i]]+=1
dnum=0
for i in xrange(n+1):
    if cnt[i]==2:
        dnum=i
        break
idx=[]
fact=[0]*(n+5)
fact[0]=1
inv=[0]*(n+5)
inv[n+1]=pow(factorial(n+1), mod - 2, mod)
for i in xrange(n+1):
    fact[i+1] = (i+1)*fact[i]%mod
for i in xrange(n, -1, -1):
    inv[i] = inv[i+1]*(i+1)%mod
for i in xrange(n+1):
    if dnum==a[i]:
        idx.append(i)

y=n-idx[1]
x=idx[0]

for i in xrange(n+1):
    #print nCk(y,i)
    print (nCk(n+1, i+1) - nCk(x+y,i))%mod

Submission status: Accepted

Solution code:
MOD = 1000000007
n = int(raw_input())
d = {}
for i, ai in enumerate(int(_) for _ in raw_input().split()):
    if ai in d:
        stt = d[ai]
        end = i
        break
    d[ai] = i
del d, i, ai

fac = {0: 1}
facinv = {}
for i in xrange(1, n + 2):
    fac[i] = fac[i - 1] * i % MOD
facinv[n + 1] = pow(fac[n + 1], MOD - 2, MOD)
for j in xrange(n, -1, -1):
    facinv[j] = facinv[j + 1] * (j + 1) % MOD


def ncr(n, r):
    return (fac[n] * facinv[n - r] * facinv[r]) % MOD


l = stt
r = n - end

for k in xrange(1, n + 2):
    a = ncr(n + 1, k) % MOD
    if l + r >= k - 1:
        a -= ncr(l + r, k - 1) % MOD
    print a % MOD

Submission status: Accepted

Solution code:
import sys
from collections import Counter

# sys.stdin = open('d1.in')
# sys.stdout = open('out.txt', 'w')

M = 10 ** 9 + 7


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    n = read_int()
    inv = [0] * (n + 2)
    inv[1] = 1
    for i in range(2, n + 2):
        inv[i] = (M - M // i) * inv[M % i] % M
    a = read_int_list()
    c = Counter(a)
    j = -1
    for i in range(1, n + 1):
        if c[i] == 2:
            j = i
            break
    p = [i for i in range(n + 1) if a[i] == j]
    d = p[1] - p[0]
    r = [0] * (n + 1)
    c = 1
    cc = 1
    for k in range(1, n + 2):
        c *= n + 1 - k + 1
        c *= inv[k]
        c %= M
        r[k - 1] = (c - cc) % M

        cc *= n - d - k + 1
        cc *= inv[k]
        cc %= M

    res = '\n'.join(map(str, r))
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# D
n = int(input())
a_list = list(map(int, input().split()))
L = 1000000007

inv_list = [0]
for i in range(1, n+2):
    inv_list.append(pow(i, L-2, L))

# find which duplicated
a_dict = dict()
for i in range(1, n+1):
    a_dict[i] = []
for i in range(n+1):
    a_dict[a_list[i]].append(i)
    if len(a_dict[a_list[i]]) == 2:
        dup = a_dict[a_list[i]]

res_list = [n]
k = (n + 1) - (dup[1] - dup[0] + 1)
ncr = n + 1
kcr = 1
for r in range(2, n+2):
    ncr *= (n+1) - (r-1)
    ncr = ncr % L
    ncr *= inv_list[r]
    ncr = ncr % L
    if k >= r-1:
        kcr *= k - (r-2)
        kcr = kcr % L
        kcr *= inv_list[r-1]
        kcr = kcr % L
    else:
        kcr = 0
    res_list.append((ncr-kcr) % L)
    
for r in range(n+1):
    print(res_list[r])

Submission status: Accepted

Solution code:
class Combin(object):
    def __init__(self, max_n, mod = 10**9 + 7):
        self.max_n = max_n
        self.mod = mod
        self.fac = self._init_factorials()
        self.inv = self._init_inv()
        
    def _init_factorials(self):
        N = self.max_n
        mod = self.mod
        f = 1
        fac = [1] * (N + 1)
        for i in range(1, N + 1):
            f *= i
            f %= mod
            fac[i] = f
        return fac

    def _init_inv(self):
        N = self.max_n
        mod = self.mod
        ret = pow(self.fac[N], mod - 2, mod)
        inv = [1] * (N + 1)
        inv[N] = ret
        for i in range(N-1, 0, -1):
            ret *= i + 1
            ret %= mod
            inv[i] = ret
        return inv

    def nCb(self, n, b):
        if b > n: return 0
        return (self.fac[n] * self.inv[b] * self.inv[n-b]) % self.mod

    def nPb(self, n, b):
        return (self.fac[n] * self.inv[n-b]) % self.mod


def find_double(n, As):
    pos = [0] * (n + 1)
    for i, a in enumerate(As, 1):
        if (pos[a - 1]):
            return pos[a - 1], i
        pos[a - 1] = i

def solve(n, As):
    mod = 10**9 + 7
    a, b = find_double(n, As)
    cb = Combin(n + 5)
    r = n + a - b
    res = [(cb.nCb(n + 1, k) - cb.nCb(r, k - 1)) % mod for k in range(1, n + 2)]
    return res

n = int(input())
As = list(map(int, input().split()))
res = solve(n, As)
for r in res:
    print(r)

Submission status: Accepted

Solution code:
n = input()
A = map(int, raw_input().split())
fact = [0]*(n+1)
frev = [0]*(n+1)
MOD = 10**9 + 7
frev[0] = fact[0] = 1

for i in xrange(1, n+1):
    fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(fact[i], MOD-2, MOD)

def comb(n, k):
    return (((fact[n] * frev[k]) % MOD) * frev[n-k]) % MOD

left = 0; right = 0
B = [0]*(n+1)
for a in A:
    B[a] += 1
p = B.index(2)
while A[left] != p:
    left += 1
while A[-1-right] != p:
    right += 1
mid = n+1 - left - right
ans = []
for k in xrange(1, n+2):
    res = 0
    if 0 <= k <= n-1:
        res += comb(n-1, k)
    if 0 <= k-1 <= n-1:
        if k-1 <= left+right:
            res += comb(left+right, k-1) + 2*(comb(n-1, k-1) - comb(left+right, k-1))
        else:
            res += 2*comb(n-1, k-1)
    if 0 <= k-2 <= n-1:
        res += comb(n-1, k-2)
    res %= MOD
    ans.append(res)
print "\n".join(map(str, ans))

Submission status: Runtime Error

Solution code:
import collections

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
K = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, K + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
n=int(input())
print(n)
nCk=n
R=list()
L=list(map(int,input().split()))
c = collections.Counter(L)
nikai=c.most_common()[0][0]#2回出てくる数
for i in range(n+1):
  if L[i]==nikai:
    R.append(i)
#Rに二個のindがある。それぞれR[0]こ、N-R[1]
k=n-R[1]+R[0]
for i in range(1,n):
  nCk=cmb(n+1,i+1,mod)
  a = cmb(k,i,mod)
  print((nCk-a)%mod)
print(1)

Submission status: Runtime Error

Solution code:
#!python3

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

# input
N = int(input())
A = LI()

MOD = 10 ** 9 + 7
MAX = 10 ** 5 + 1
fac, finv, inv = [None] * MAX, [None] * MAX, [None] * MAX


def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = -inv[MOD%i] * int(MOD / i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


def main():
    comb_init()
    d = {i: [] for i in range(1, N + 1)}
    x, y = [None] * 2
    for i in range(N + 1):
        d[A[i]].append(i)
        if len(d[A[i]]) == 2:
            x, y = d[A[i]]
            break
    
    for i in range(1, N + 2):
        ans = comb(N + 1, i)
        ans -= comb(N + x - y, i - 1)
        ans %= MOD
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;

struct Combination{
    Int MOD, MAX_N;
    vector<Int> f, f_inv;

    //---------- 初期化 ----------
    Combination(Int mod = 1e9+7, Int max_n = 1e7){
        MOD = mod;
        MAX_N = max_n;

        f = factorial(MAX_N);
        rep(i,f.size()) f_inv.push_back(inv(f[i]));
    }
    
    //------- べき乗 a^n -------
    Int power(Int a, Int n){
        if(a == 0) return 0;
        if(n == 0) return 1;

        Int res = 1;
        while(n > 0){
            if(n % 2 == 1) res = res * a % MOD;
            a = a * a % MOD; n /= 2;
        }
        return res;
    }

    //------- 逆元 1/a -------
    Int inv(Int a){
        return power(a, MOD-2);
    }

    //------- 階乗 (nまでの階乗の配列を返す) -------
    vector<Int> factorial(Int n){
        vector<Int> res(n+1, 1);
        rep1(i,n) res[i] = i * res[i-1] % MOD;

        return res;
    }


    //------- 組み合わせ nCr -------
    Int comb(Int n, Int r){
        return (f[n] * f_inv[r] % MOD ) * f_inv[n-r] % MOD;
    }
};

int main(){
    Int N, twice, p;
    cin >> N;

    vector<Int> A(N+1), cnt(N,0);
    rep(i,N){
        cin >> A[i];
        cnt[A[i]-1]++;
        if(cnt[A[i]-1] == 2){
            twice = A[i];
            p = i;
        }
    }

    Combination C(1e9+7, 1e5+10);
    rep1(k,N+1){
        if(k == 1){
            cout << N << endl;
            continue;
        }

        Int ans = C.comb(N+1, k);
        if(N+1-p >= k) ans += C.MOD - C.comb(N+1-p, k);
        ans %= C.MOD;
        cout << ans << endl;
    }
}

Submission status: Runtime Error

Solution code:
n=int(input())
A=list(map(int, input().split()))
B=sorted(A)
for i in range(n+1):
  if B[i]!=i+1:
    a=i
    break
d=[i for i, x in enumerate(A) if x==a]
x=d[0]
y=d[1]

def cmb(n,r,mod):
    if (r<0 or r>n):
      return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod

mod=10**9+7 #出力の制限
N=10**5
g1=[1,1] # 元テーブル
g2=[1,1] #逆元テーブル
inverse=[0,1] #逆元テーブル計算用テーブル

for i in range(2,N+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

for i in range(1,n+2):
  print(cmb(n+1,i,mod)-cmb(x+(n-y),i-1,mod))

Submission status: Runtime Error

Solution code:
n=int(input())
A=list(map(int, input().split()))
B=sorted(A)
for i in range(n+1):
  if B[i]!=i+1:
    a=i
    break
d=[i for i, x in enumerate(A) if x==a]
x=d[0]
y=d[1]

def cmb(n,r,mod):
    if (r<0 or r>n):
      return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod

mod=10**9+7 #出力の制限
N=10**4
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)

for i in range(1,n+2):
  print(cmb(n+1,i,mod)-cmb(x+(n-y),i-1,mod))

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

f = [0 for _ in range(200000)]
f[0] = 1
for i in range(1, 200000):
    f[i] = f[i - 1] * i % mod
inv = [pow(f[i], mod - 2, mod) for i in range(200000)]


def C(n, m):
    if n < m: return 0
    return f[n] * inv[m] * inv[n - m]

n = int(input())
a = [*map(lambda x: int(x) - 1, input().split())]
pos = [[] for _ in range(n)]

for idx, x in enumerate(a):
    pos[x].append(idx)

for _ in pos:
    if len(_) == 2:
        l, r = _

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

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

f = [0 for _ in range(100000)]
f[0] = 1
for i in range(1, 100000):
    f[i] = f[i - 1] * i % mod
inv = [pow(f[i], mod - 2, mod) for i in range(100000)]


def C(n, m):
    if n < m: return 0
    return f[n] * inv[m] * inv[n - m]

n = int(input())
a = [*map(lambda x: int(x) - 1, input().split())]
pos = [[] for _ in range(n)]

for idx, x in enumerate(a):
    pos[x].append(idx)

for _ in pos:
    if len(_) == 2:
        l, r = _

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

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

f = [0 for _ in range(100000)]
f[0] = 1
for i in range(1, 100000):
    f[i] = f[i - 1] * i % mod
inv = [pow(f[i], mod - 2, mod) for i in range(100000)]


def C(n, m):
    if n < m: return 0
    return f[n] * inv[m] * inv[n - m]

n = int(input())
a = [*map(lambda x: int(x) - 1, input().split())]
pos = [[] for _ in range(n)]

for idx, x in enumerate(a):
    pos[x].append(idx)

for _ in pos:
    if len(_) == 2:
        l, r = _

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

Submission status: Runtime Error

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

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

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, = map(int, input().split())
ps = list(map(int, input().split()))
p2i = dict()
i = 0
for p in ps:
    if p not in p2i:
        i += 1
        p2i[p] = i
        continue
    x = p2i[p]
    break
X = min(x-1, i-1)
Y = min(N-x, N-i)
for i in range(1, N+2):
    print((cmb(N+1, i) - cmb(X+Y, i-1))%mod)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from collections import deque

class SegTree():
    def __init__(self, n):
        self.value = [0 for i in range(n*2)]

MOD = 10 ** 9 + 7

def getinvmod(n):
    return [pow(i, MOD-2, MOD) for i in range(n+1)]


def main():
    n = getN()
    nums = getList()
    index = [0 for i in range(n)]

    for i, num in enumerate(nums):
        if index[num - 1] == 0:
            index[num - 1] = i
        else:
            ida = i
            idb = index[num - 1]
            break

    side = n - (ida - idb)

    invmod = getinvmod(n+1)

    # print(invmod)
    #
    # print([(i * iv) % MOD for i, iv in enumerate(invmod)])
    ans = n + 1
    minus = 1
    print((ans - minus)%MOD)
    # print(side, ida, idb,"side")
    for i in range(1, n + 1):
        ans *= (n - i + 1)
        ans *= invmod[i + 1]
        ans %= MOD
        if i <= side:
            minus *= side - i + 1
            minus *= invmod[i]
            minus %= MOD

        else:
            minus = 0

        print((ans - minus) % MOD)
        # print(ans, minus)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    a = LI()
    d = defaultdict(lambda:0)
    for i in a:
        d[i] += 1
    d = list(d.values())
    d.sort()
    ans = 0
    for i in range(len(d)-k):
        ans += d[i]
    print(ans)
    return

#B
def B():
    n,z,w = LI()
    a = LI()
    if n == 1:
        print(abs(a[0]-w))
        return
    ans = max(abs(a[-1]-w),abs(a[-2]-a[-1]))
    print(ans)
    return

#C
def C():
    n = I()
    s1 = S()
    s2 = S()
    dp = [[[0]*3 for j in range(3)] for i in range(n+1)]
    if s1[0] == s2[0]:
        dp[1] = [[1 if i == j else 0 for j in range(3)] for i in range(3)]
    else:
        dp[1] = [[0 if i == j else 1 for j in range(3)] for i in range(3)]
    for i in range(1,n):
        ni = i+1
        if s1[i] == s2[i]:
            for j in range(3):
                for k in range(3):
                    if k == j:continue
                    for l in range(3):
                        if l == j:continue
                        dp[ni][j][j] += dp[i][k][l]
        else:
            if i and s1[i] == s1[i-1]:
                for j in range(3):
                    for k in range(3):
                        dp[ni][j][k] = dp[i][j][k]
            else:
                for j in range(3):
                    for k in range(3):
                        if k == j:continue
                        for l in range(3):
                            if l == j:continue
                            for m in range(3):
                                if m == k:continue
                                dp[ni][j][k] += dp[i][l][m]
    ans = 0
    for i in range(3):
        for j in range(3):
            ans += dp[n][i][j]
    print(ans%mod)
    return

#D
def D():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod
    n = I()
    a = LI()
    d = defaultdict(lambda : 0)
    for i in range(n+1):
        if d[a[i]]:
            l = d[a[i]]-1
            r = n-i
            break
        d[a[i]] = i+1
    fact = [1]
    m = 100000
    for i in range(m):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(m+1)
    inv[m] = pow(fact[m],mod-2,mod)
    for i in range(m)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    for i in range(1,n+2):
        ans = comb(n+1,i)
        if l+r >= i-1:
            ans -= comb(l+r,i-1)
            ans %= mod
        print(ans)
    return

#E
def E():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Runtime Error

Solution code:
N=int(input())
a=[int(i)-1 for i in input().split()]
count=[0]*N
for i in range(N):
  count[a[i]]+=1
  if count[a[i]]==2:
    D=a[i]
    break
flag=False
k=0
mod=10**9+7
for i in range(N+1):
  if a[i]==D and not flag:
    flag=True
  elif a[i]==D and flag:
    break
  elif flag:
    k+=1
    
Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
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

inverseFactorial=[1]*(N+1)
inverseFactorial[N]=power(Factorial[N],mod-2)
for i in range(0,N)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod

dp=[[0]*3 for i in range(N+2)]
dp[0][0]=1

for i in range(N+1):
  dp[i+1][0]=comb(N-1,i+1)
  dp[i+1][1]=-comb(N-k-1,i)+2*dp[i][0]
  if i>=1:
    dp[i+1][2]=dp[i-1][0]
  print(sum(dp[i+1])%mod)