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:
# ------ combination -------
N, MOD = 10**5 + 1, 10**9 + 7
fc, ifc = [0] * (N+1), [0] * (N+1)

def power(n, a):
    res, exp = 1, n
    while(a):
        if a & 1:
            res = res * exp % MOD
        exp = exp * exp % MOD
        a = a >> 1
    return res

fc[0] = 1
for i in range(1, N+1):
    fc[i] = fc[i-1] * i % MOD
ifc[N] = power(fc[N], MOD-2)
for i in range(N-1, -1, -1):
    ifc[i] = ifc[i+1] * (i+1) % MOD

def Comb(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    return fc[n] * ifc[r] % MOD * ifc[n-r] % MOD

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

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

num = [-1] * (n+1)
l = r = -1
for i in range(len(a)):
    if num[a[i]] != -1:
        l, r = num[a[i]], i
        break
    num[a[i]] = i

for k in range(1, len(a)+1):
    ans = Comb(len(a), k) - Comb(l+len(a)-r-1, k-1)
    while ans < 0:
        ans += MOD
    print(ans)

Submission status: Accepted

Solution code:

MOD = 10**9+7
n = int(input())
la = list(map(int,input().split()))
L = [-1]*(n+1)
l = 0
for i in range(n+1):
  a = la[i]
  if L[a] == -1:
    L[a] = i
  else:
    l = i - L[a] - 1
    break
 
MAX = n
factorial = [1, 1]
inverse = [0, 1]
inverse_factorial = [1, 1]
for i in range(2,MAX+1):
  factorial.append( (factorial[-1]*i)%MOD )
  inverse.append( (-inverse[MOD%i]*(MOD//i))%MOD )
  inverse_factorial.append( (inverse_factorial[-1]*inverse[-1])%MOD )
 
def C_MOD(n, k):
  if k < 0 or k > n:
    return 0
  k = min(k,n-k)
  return factorial[n] * inverse_factorial[k] * inverse_factorial[n-k] % MOD
 
print(n)
#print((2*C_MOD(n-1,1)-C_MOD(n-1-l,1)+C_MOD(n-1,2)+1)%MOD)
for i in range(2,n+1):
  if n > l+1:
    print((2*C_MOD(n-1,i-1)-C_MOD(n-1-l,i-1)+C_MOD(n-1,i)+C_MOD(n-1,i-2))%MOD)
  else:
    print((2*C_MOD(n-1,i-1)+C_MOD(n-1,i)+C_MOD(n-1,i-2))%MOD)
print(1)

Submission status: Accepted

Solution code:
from collections import Counter

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

counter = Counter(src)
dup = counter.most_common(1)[0][0]
a = src.index(dup)
b = a+1 + src[a+1:].index(dup)
arr = src[:a] + src[b+1:]
n2 = len(arr)

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

def pow(a,n):
  ans = 1
  mag = a
  for b in reversed(str(bin(n))):
    if b == 'b': break
    if b == '1':
      ans = mul(ans, mag)
    mag = mul(mag, mag)
  return ans

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

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

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

for i in range(N+1):
    ans = ncr(N+1, i+1)
    if i <= n2:
        ans = (ans - ncr(n2, i)) % MOD
    print ans

Submission status: Accepted

Solution code:
MOD = 10**9+7
n = int(input())
la = list(map(int,input().split()))
L = [-1]*(n+1)
l = 0
for i in range(n+1):
  a = la[i]
  if L[a] == -1:
    L[a] = i
  else:
    l = i - L[a] - 1
    break

MAX = n
factorial = [1, 1]
inverse = [0, 1]
inverse_factorial = [1, 1]
for i in range(2,MAX+1):
  factorial.append( (factorial[-1]*i)%MOD )
  inverse.append( (-inverse[MOD%i]*(MOD//i))%MOD )
  inverse_factorial.append( (inverse_factorial[-1]*inverse[-1])%MOD )

def C_MOD(n, k):
  if k < 0 or k > n:
    return 0
  k = min(k,n-k)
  return factorial[n] * inverse_factorial[k] * inverse_factorial[n-k] % MOD

print(n)
#print((2*C_MOD(n-1,1)-C_MOD(n-1-l,1)+C_MOD(n-1,2)+1)%MOD)
for i in range(2,n+1):
  if n > l+1:
    print((2*C_MOD(n-1,i-1)-C_MOD(n-1-l,i-1)+C_MOD(n-1,i)+C_MOD(n-1,i-2))%MOD)
  else:
    print((2*C_MOD(n-1,i-1)+C_MOD(n-1,i)+C_MOD(n-1,i-2))%MOD)
print(1)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import Counter
two=0
a=Counter(A)
for k,v in a.items():
  if v==2:
    two=k
LR=[]
for i in range(N+1):
  if A[i]==two:
    LR.append(i)
L=LR[0]
R=LR[1]
mod=10**9+7
P=[1 for i in range(10**6+1)]
for i in range(10**6):
  P[i+1]=P[i]*(i+1)%mod
L+=1
R+=1
def comb(a,b):
  if a>=b:
    return P[a]*pow(P[a-b],mod-2,mod)*pow(P[b],mod-2,mod)%mod
  else:
    return 0

for i in range(1,N+2):
  print((comb(N+1,i)-comb(N+L-R,i-1))%mo

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import Counter
two=0
a=Counter(A)
for k,v in a.items():
  if v==2:
    two=k
LR=[]
for i in range(N):
  if A[i]==two:
    LR.append(i)
L=LR[0]
R=LR[1]
mod=10**9+7
P=[1 for i in range(10**6+1)]
for i in range(10**6):
  P[i+1]=P[i]*(i+1)%mod
L+=1
R+=1
def comb(a,b):
  if a>=b:
    return P[a]*pow(P[a-b],mod-2,mod)*pow(P[b],mod-2,mod)%mod
  else:
    return 0

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

Submission status: Runtime Error

Solution code:
import itertools

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

MOD = 10**9 + 7
MAX_NUM = 10**5

def inv_mod(n):
  return pow(n, MOD-2, MOD)

FACTS = [1 for _ in range(MAX_NUM+1)]
for n in range(1, MAX_NUM+1):
  FACTS[n] = (n*FACTS[n-1]) % MOD

INV_FACTS = [1 for _ in range(MAX_NUM+1)]
INV_FACTS[MAX_NUM] = inv_mod(FACTS[MAX_NUM])
for n in range(MAX_NUM-1, -1, -1):
  INV_FACTS[n] = (INV_FACTS[n+1]*(n+1)) % MOD
  
for i in range(MAX_NUM+1):
  assert (FACTS[i]*INV_FACTS[i])%MOD == 1

def ncr(n, r):
  if r > n:
    return 0
  if r < 0:
    return 0
  # C(n, r) = n!/(n-r)!r!
  ans = FACTS[n]*INV_FACTS[n-r]*INV_FACTS[r]
  return ans % MOD

from collections import defaultdict
v2i = defaultdict(list)
for i, v in enumerate(A):
  v2i[v].append(i)

fst, snd = -1, -1
for v in v2i:
  if len(v2i[v]) == 2:
    fst, snd = v2i[v]

K = snd - fst - 1
for ell in range(1, N+2):
  ans = ncr(N+1, ell) - ncr(N-1-K, ell-1)
  print(ans%MOD)

Submission status: Runtime Error

Solution code:
import iterools

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

for i in range(n+1):
  if i == len(n):
    print(1)
  else:
    combos = list(itertools.combinations(a, i))
    print(len(set(combos)))

Submission status: Runtime Error

Solution code:
import iterools

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

for i in range(n):
  if i == len(n)-1:
    print(1)
  else:
    combos = itertools.combinations(a, i)
    print(len(set(combos)))

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    pre_idx = 0
    idx = 0
    appeared = [-1] * (N + 1)
    for i, a in enumerate(A):
        if appeared[a] == -1:
            appeared[a] = i
        else:
            pre_idx, idx = appeared[a], i
            break

    # dp[i][j] = (A[:i]まで見た時にj個数字を選んでできる部分列の種類)
    dp = [[0] * (N + 2) for _ in range(N + 2)]
    for i in range(N + 2): dp[i][i] = 1
    for i in range(N + 2): dp[i][0] = 1
    for i in range(1, N + 2):
        if i - 1 != idx:
            for j in range(1, i):
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod
        else:
            for j in range(1, pre_idx + 2):
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] - dp[pre_idx][j - 1]) % mod
            for j in range(pre_idx + 2, i):
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod
    #for i in range(1, N + 2): print("A[:{}] => dp[{}]={}".format(i, i, dp[i]))
    for k in range(1, N + 2):
        print(dp[N + 1][k])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    pre_idx = 0
    idx = 0
    appeared = [-1] * (N + 1)
    for i, a in enumerate(A):
        if appeared[a] == -1:
            appeared[a] = i
        else:
            pre_idx, idx = appeared[a], i
            break
    print("pre_idx={}, idx={}".format(pre_idx, idx))

    # dp[i][j] = (A[:i]まで見た時にj個数字を選んでできる部分列の種類)
    dp = [[0] * (N + 2) for _ in range(N + 2)]
    for i in range(N + 2): dp[i][i] = 1
    for i in range(N + 2): dp[i][0] = 1
    for i in range(1, N + 2):
        if i - 1 != idx:
            for j in range(1, i):
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod
        else:
            for j in range(1, pre_idx + 2):
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] - dp[pre_idx][j - 1]) % mod
            for j in range(pre_idx + 2, i):
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod
    #for i in range(1, N + 2): print("A[:{}] => dp[{}]={}".format(i, i, dp[i]))
    for k in range(1, N + 2):
        print(dp[N + 1][k])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    sn=pk[0]+n-pk[1]
    for i in range(n):
        ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
        ans1[i+1]=ans0[i]*2-(sn>i)*(fact[sn]*ifact[sn-i]*ifact[i] % p)
        ans2[i+2]=ans0[i]import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    sn=pk[0]+n-pk[1]
    for i in range(0,n+2):
        if i<n:
            ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
            ans1[i+1]=ans0[i]*2-(sn>=i)*(fact[sn]*ifact[sn-i]*ifact[i] % p)
            ans2[i+2]=ans0[i]
        if i>0:
            print((ans0[i]+ans1[i]+ans2[i]) % p)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    sn=pk[0]+n-pk[1]
    for i in range(n):
        ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
        ans1[i+1]=ans0[i]*2-(sn>i)*(fact[sn]*ifact[sn-i]*ifact[i] % p)
        ans2[i+2]=ans0[i]import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    sn=pk[0]+n-pk[1]
    for i in range(0,n+2):
        if i<n:
            ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
            ans1[i+1]=ans0[i]*2-(sn>=i)*(fact[sn]*ifact[sn-i]*ifact[i] % p)
            ans2[i+2]=ans0[i]
        if i>0:
            print((ans0[i]+ans1[i]+ans2[i]) % p)

if __name__=='__main__':
    main()

        print((ans0[i]+ans1[i]+ans2[i]) % p)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    sn=pk[0]+n-pk[1]
    for i in range(n):
        ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
        ans1[i+1]=ans0[i]*2
        ans2[i+2]=ans0[i]
		if sn>i:
            ans1[i+1]-=fact[sn]*ifact[sn-i]*ifact[i] % p
        print((ans0[i]+ans1[i]+ans2[i]) % p)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
def comb(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)


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

appeared = set()
dup_right = 0
dup = 0
for i, x in enumerate(a):
    if x in appeared:
        dup_right = n - i
        dup = x
        break
    appeared.add(x)
dup_left = 0
for i, x in enumerate(a):
    if x == dup:
        dup_left = i
        break

print("dup_right", dup_right)
print("dup_left", dup_left)

print(n)
for i in range(2, n + 2):
    res = comb(n + 1, i, MOD)
    if dup_right + dup_left >= i - 1:
        res = res - comb(dup_right + dup_left, i - 1, MOD) % MOD
    print(res)

Submission status: Runtime Error

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def comb(n,k):
    ret = fact[n]*modinv2(fact[n-k]*fact[k],R)%R
    ddprint(f"comb {n=} {k=} {ret=}")
    return ret

n = inn()
a = inl()
fact = [1]*(n+1)
for i in range(1,n+1):
    fact[i] = (fact[i-1]*i)%R
ddprint(fact)
c = [-1]*(n+1)
for m in range(n+1):
    x = a[m]
    if c[x]>=0:
        i = c[x]
        j = m+1
        break
    c[x] = m+1
#ddprint(f"{n=} {i=} {j=}")
print(n) # k=1
for k in range(2,n):
    #ddprint(f"{k=}")
    v0 = comb(n-1,k) if k<=n-1 else 0
    #ddprint(f"{v0=}")
    v2 = comb(n-1,k-2) if k>=2 else 0
    #ddprint(f"{v2=}")
    v1 = 2*comb(n-1,k-1) - \
         (0 if n-j+i<k-1 else comb(n-j+i,k-1))
    #ddprint(f"{k=} {v0=} {v1=} {v2=}")
    print((v0+v1+v2)%R)
if n>1:
    print(n if j==i+1 else n+1) # k=n
print(1) # k=n+1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0




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

lst = [-1] * (N + 1)
for i in range(N):
    a = A[i]
    if lst[a] == -1:
        lst[a] = i
    else:
        left = lst[a]
        right = i
        break
# print (left, right)
F = Factorial(N + 1, MOD).comb

for i in range(1, N + 2):
    if left + N - right >= i - 1:
        tmp = F(N + 1, i) - F(left + (N- right), i - 1)
    else:
        tmp = F(N + 1, i)
    print (tmp % MOD)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0




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

lst = [-1] * (N + 1)
for i in range(N):
    a = A[i]
    if lst[a] == -1:
        lst[a] = i
    else:
        left = lst[a]
        right = i
        break
# print (left, right)
F = Factorial(N + 1, MOD).comb

for i in range(1, N + 2):
    tmp = F(N + 1, i) - F(left + (N- right), i - 1)
    
    print (tmp % MOD)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline


def solve():
    N = int(input())
    d = {i:-1 for i in range(1, N+1)}
    *l, = map(int, input().split())

    MOD = 10**9+7
    n = N+1
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
    fac[i] = i*fac[i-1]%MOD
    rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD if a>=b else 0

    for i, j in enumerate(l):
        if d[j] != -1:
            break
        d[j] = i

    v = d[j]+N-i
    for i in range(1, N+2):
        print((comb(N+1, i)-comb(v, i-1))%MOD)


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
N = int(input())
d = {i:-1 for i in range(1, N+1)}
*l, = map(int, input().split())

MOD = 10**9+7
n = N+1
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD if a>=b else 0

for i, j in enumerate(l):
    if d[j] != -1:
        break
    d[j] = i

for i in range(1, N+2):
    print((comb(N+1, i)-comb(d[j]+N-1, i-1))%MOD)

Submission status: Runtime Error

Solution code:
N = int(input())
d = {i:-1 for i in range(1, N+1)}
*l, = map(int, input().split())

MOD = 10**9+7
n = N+1
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD if a>=b else 0

for i, j in enumerate(l):
    if d[j] != -1:
        break
    d[j] = i

for i in range(1, N+2):
    print((comb(N+1, i)-comb(d[j]+N-1, i-1))%MOD)

Submission status: Runtime Error

Solution code:
n= int(input())
a= list(map(int,input().split()))
check = [0]*(n+1)
g1=[1,1]
g2=[1,1]
inverse=[0,1]
for i in range(2,n+1+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)
def cmb2(n,r):
    mod = 1000000007
    if (r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%mod
r=-1
jn=-1
for i in range(n+1):
    check[a[i]-1]+=1
    if check[a[i]-1]==2:
        jn,r=a[i],i
        break
l=a.index(jn)
s,t=l,n-r
print(n)
for k in range(2,n+1):
    w2=cmb2(n+1,k)
    if s+t>=k-1:w2-=cmb2(s+t,k-1)
    print(w2)
print(1)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)
for i in range(n):
    if b[a[i]] == 0:
        b[a[i]] += 1
    else:
        d = a[i]

l = 0
r = 0
c = 0
for i in range(n+1):
    if a[i] != d and c == 0:
        l += 1
    elif a[i] != d and c == 2:
        r += 1
    if a[i] == d:
        c += 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 = 100001
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 )


print(n)
for i in range(2, n+2):
    print(cmb(n+1, i, mod)-max(0, r-i+2)-max(0, l-i+2))

Submission status: Runtime Error

Solution code:
N, *X = map(int, open(0).read().split())

MAX = 10 ** 5
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

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

# Find indices of duplicated values
indices = [-1] * (N + 1)
for i in range(N + 1):
    if indices[X[i]] < 0:
        indices[X[i]] = i
    else:
        l = indices[X[i]]
        r = i
        break

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

Submission status: Runtime Error

Solution code:
# 繰り返し二乗法 (mod 有り)
def mod_rep_pow(a, n, mod=(10 ** 9 + 7)):
    res = 1
    while n > 0:
        if n % 2 == 0:
            a = a ** 2 % mod
            n //= 2
        else:
            res = res * a % mod
            n -= 1
    return (res % mod)


# 繰り返し二乗法 (mod 有り) を利用して nCk を高速に返す
# mod が素数のときのみ利用可能 (フェルマーの小定理を利用しているため)
def mod_comb(n, k, mod=(10 ** 9 + 7)):
    res1 = 1
    for i in range(n, (n - k), -1):
        res1 *= i
        res1 %= mod
    res2 = 1
    for i in range(1, (k + 1)):
        res2 *= i
        res2 %= mod
    return ((res1 * mod_rep_pow(res2, (mod - 2), mod)) % mod)


n = int(input().strip())
a = list(map(int, input().split()))
not_unique = sum(a) - sum([i for i in range(1, n + 1)])
b = []
for i in range(n + 1):
    if a[i] == not_unique:
        b.append(i)
x = n - (b[1] - b[0])

for i in range(1, n + 2):
    print(mod_comb(n + 1, i)  # - mod_comb(x, (i - 1)))

Submission status: Runtime Error

Solution code:
mod = 10**9+7
MAX = 10**5
fact = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i)%mod
inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[mod%i]*(mod-mod//i)%mod
fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1]*inv[i]%mod
def comb(n, r):
    if n < r:
        return 0
    return fact[n]*fact_inv[n-r]*fact_inv[r] % mod

n = int(input())
L = list(map(int,input().split()))
M = []
for i in range(n+1):
    M.append(L[i])
M.sort()
dou = 1 #重複する数
for i in range(n+1):
    if M[i] == dou:
        dou += 1
    else:
        dou = M[i]
        break
l = 0
r = 0
cnt = 0
for i in range(n+1):
    if L[i] == dou and cnt == 0:
        l = i+1
        cnt += 1
    elif L[i] == dou and cnt == 1:
        r = i+1
        break
for i in range(1,n+1):
    print((comb(n+1,i)-comb(l+n-r,i-1))%mod)
print(1)

Submission status: Runtime Error

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

MOD = 10**9 + 7
N = 10**5

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

from collections import defaultdict
dic = defaultdict(int)

v = 0
s = 0
e = 0
for idx, a in enumerate(al):
    if dic[a] == 1:
        e = idx
        v = a
    dic[a] += 1

for idx, a in enumerate(al):
    if a == v:
        s = idx
        break


for i in range(1, n+2):
    ans = comb(n+1, i)
    if s + n - e >= i - 1:
        ans -= comb(s+(n-e), i-1)
    ans %= MOD
    print(ans)

Submission status: Runtime Error

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

MOD = 10**9 + 7
N = 10**5

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

from collections import defaultdict
dic = defaultdict(int)

for idx, a in enumerate(al):
    if dic[a] == 1:
        e = idx
        v = a
    dic[a] += 1

for idx, a in enumerate(al):
    if a == v:
        s = idx
        break


for i in range(1, n+2):
    ans = comb(n+1, i)
    if s + n - e >= i - 1:
        ans -= comb(s+(n-e), i-1)
    ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
p = 10**9+7

n = int(input())
a = list( map(int, input().split()))
count = [0]*n

for i in range(n+1):
    count[a[i]-1] += 1
    if count[a[i]-1] == 2:
        right = i
        left = a.index(a[i])
        break

def nCr_mod_p(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p), 0! = 1! = 1
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p), 0! = 1! = 1
inv = [0, 1]  # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
p = 10**9+7

n = int(input())
a = list( map(int, input().split()))
count = [0]*n

for i in range(n+1):
    count[a[i]-1] += 1
    if count[a[i]-1] == 2:
        right = i
        left = a.index(a[i])
        break

print(left,right)

def nCr_mod_p(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p), 0! = 1! = 1
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p), 0! = 1! = 1
inv = [0, 1]  # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

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

Submission status: Runtime Error

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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 )

ma=0
dic={}
for i in range(m):
    if not a[i] in dic:
        dic[a[i]]=i
    else:
        ma=i-dic[a[i]]-1

for k in range(1,m+1):
    if k==1:
        print(n)
        continue
    tmp=cmb(m,k)
    if m-2-ma>=k-1:
        tmp-=cmb(m-2-ma,k-1)
    print(tmp%mod)

Submission status: Runtime Error

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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 )

ma=0
dic={}
for i in range(m):
    if not a[i] in dic:
        dic[a[i]]=i
    else:
        ma=i-dic[a[i]]-1

for k in range(1,m+1):
    if k==1:
        print(n)
        continue
    tmp=(cmb(m,k)
    if m-2-ma>=k-1:
        tmp-=cmb(m-2-ma,k-1)
    print(tmp%mod)