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:
import collections

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

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

mod = 1e9 + 7
n = int(input())
a = list(map(int,input().split()))
c = collections.Counter(a)
two = 0
for i in c:
    if c[i] == 2:
        two = i
before = 0
later = 0
temp = 0
for i in range(n+1):
    if temp == 2:
        later += 1
    if a[i] == two:
        temp += 1
    if temp == 0:
        before += 1

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

Submission status: Runtime Error

Solution code:
# ARC 77 D
MOD = 10**9 + 7
n = int(input())
A = list(map(int, input().split()))

fact = {i: None for i in range(n+1)}                 # n!
inverse = {i: None for i in range(1, n+1)}       # inverse of n in the field Z/(MOD)Z
fact_inverse = {i: None for i in range(n+1)}  # inverse of n! in the field Z/(MOD)Z

fact[0] = fact[1] = 1
fact_inverse[0] = fact_inverse[1] = 1
inverse[1] = 1
for i in range(2, n+1):
    fact[i] = i * fact[i-1] % MOD
    inverse[i] = - inverse[MOD % i] * (MOD // i) % MOD
    fact_inverse[i] = inverse[i] * fact_inverse[i-1] % MOD

def combination(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return fact[n] * (fact_inverse[r] * fact_inverse[n-r] % MOD) % MOD

dup_num = sum(A) - n*(n+1)//2
dup_idx = []
for i, a in enumerate(A):
    if a == dup_num:
        dup_idx.append(i)
        
left, right = dup_idx[0], dup_idx[1]
        
for k in range(1, n+2):
    print((combination(n+1, k) - combination(n + 1 - (right - left + 1), k - 1)) % MOD)

Submission status: Runtime Error

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

c = [1,n-1]
#c[i]:n-1 C i
for i in range(1,n+1):
    if n < i+2:
        c.append(0)
    else:
        r = (c[-1]*(n-1-i)//(i+1))
        c.append(r)
k = sum(a)- n*(n+1)//2

pp = []
for i in range(n+1):
    if a[i] == k:
        pp.append(i)
w = pp[1]-pp[0]-1

d = [1,n-w-1]
#d[i]:n-w-1 C i
for i in range(1,n+1):
    if n-w-1  < i+1:
        d.append(0)
    else:
        r = (d[-1]*(n-w-1-i)//(i+1))
        
        d.append(r)
for i in range(len(c)):
    c[i] = c[i]%(10**9+7)
    d[i] = d[i]%(10**9+7)
    

print(n)
for i in range(2,n+2):
    #nagasa k

Submission status: Runtime Error

Solution code:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;

public class Main {

	static PrintWriter out;
	static InputReader ir;
	static boolean debug = false;

	static void solve() {
		int n = ir.nextInt();
		int[] a = ir.nextIntArray(n + 1);
		int[] ct = new int[n + 1];
		for (int i = 0; i <= n; i++)
			ct[a[i]]++;
		int x = -1;
		for (int i = 1; i <= n; i++) {
			if (ct[i] == 2) {
				x = i;
				break;
			}
		}
		int l = -1, r = -1;
		for (int i = 0; i <= n; i++) {
			if (a[i] == x) {
				if (l == -1)
					l = i;
				else
					r = i;
			}
		}
		long mod = (long) 1e9 + 7;
		long[] f = fact(n + 1, mod), fi = factInv(n + 1, mod);
		for (int j = 1; j <= n + 1; j++) {
			long ret = comb(n - 1, j, f, fi, mod) + comb(n - 1, j - 2, f, fi, mod) + 2 * comb(n - 1, j - 1, f, fi, mod)
					- comb(n - r + l, j - 1, f, fi, mod);
			ret %= mod;
			out.println(ret);
		}
	}

	public static long mod_inverse(long a, long MOD) {
		long[] ret = extgcd(a, MOD);
		return (MOD + ret[0] % MOD) % MOD;
	}

	public static long[] extgcd(long a, long b) {
		long[] ret = new long[3];
		ret[2] = _extgcd(a, b, ret);
		return ret;
	}

	private static long _extgcd(long a, long b, long[] x) {
		long g = a;
		x[0] = 1;
		x[1] = 0;
		if (b != 0) {
			g = _extgcd(b, a % b, x);
			long temp = x[0];
			x[0] = x[1];
			x[1] = temp;
			x[1] -= (a / b) * x[0];
		}
		return g;
	}

	private static long[] fact(int n, long MOD) {
		long[] ret = new long[n + 1];
		ret[0] = 1 % MOD;
		for (int i = 1; i <= n; i++) {
			ret[i] = ret[i - 1] * i;
			ret[i] %= MOD;
		}
		return ret;
	}

	private static long[] factInv(int n, long MOD) {
		long[] ret = new long[n + 1];
		ret[0] = 1;
		for (int i = 1; i <= n; i++) {
			ret[i] = ret[i - 1] * mod_inverse((long) i, MOD) % MOD;
		}
		return ret;
	}

	public static long comb(int n, int m, long[] fact, long[] factInv, long MOD) {
		if (m < 0 || m > n)
			return 0;
		long ret = fact[n];
		ret *= factInv[m];
		ret %= MOD;
		ret *= factInv[n - m];
		ret %= MOD;
		return ret;
	}

	public static void main(String[] args) {
		ir = new InputReader(System.in);
		out = new PrintWriter(System.out);
		solve();
		out.flush();
	}

	static class InputReader {

		private InputStream in;
		private byte[] buffer = new byte[1024];
		private int curbuf;
		private int lenbuf;

		public InputReader(InputStream in) {
			this.in = in;
			this.curbuf = this.lenbuf = 0;
		}

		public boolean hasNextByte() {
			if (curbuf >= lenbuf) {
				curbuf = 0;
				try {
					lenbuf = in.read(buffer);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return false;
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[curbuf++];
			else
				return -1;
		}

		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}

		private void skip() {
			while (hasNextByte() && isSpaceChar(buffer[curbuf]))
				curbuf++;
		}

		public boolean hasNext() {
			skip();
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (!isSpaceChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public int nextInt() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}

		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public char[][] nextCharMap(int n, int m) {
			char[][] map = new char[n][m];
			for (int i = 0; i < n; i++)
				map[i] = next().toCharArray();
			return map;
		}
	}

	static void tr(Object... o) {
		if (debug)
			out.println(Arrays.deepToString(o));
	}
}

Submission status: Runtime Error

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
deni=[1]*(N+1)#(k)!を格納
quot=[1]*(N+1)#(k)!の逆数を格納
for i in range(1,N+1):
    deni[i]=(deni[i-1]*(i+1))%mod
for i in range(1,N+1):
    t=pow(i+1,mod-2,mod)
    quot[i]=(quot[i-1]*t)%mod
deni=[1]+deni
quot=[1]+quot
box=[[0,0]]*(N+1)
for i in range(N):
    if box[A[i]-1][0]==1:
        k_1=box[A[i]-1][1]
        k_2=N-i
        break
    box[A[i]-1]=[1,i]
K=k_1+k_2
ans =[]
for k in range(1,N+2):
    if k==1:
        ans.append(N)
    elif K>=k-1:
        s=deni[N+1]
        s=(s*quot[k])%mod
        s=(s*quot[N+1-k])%mod
        t=deni[K]
        t=(t*quot[k-1])%mod
        t=(t*quot[K-k+1])%mod
        #print(s,t)
        ans.append((s-t)%mod)
    else:
        s=deni[N+1]
        s=(s*quot[k])%mod
        s=(s*quot[N-k+1])%mod
        #print(s)
        ans.append(s)
#print(ans)
print('\n'.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
MOD = (10 ** 9) + 7

f_list = [1] * 100001
f_r_list = [1] * 100001

for i in range(100000):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, 100002)
	f_r_list[-i] = int((f_r_list[-i + 1] * (100003 - i)) % MOD)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

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


doubled = sum(a) - n * (n + 1) / 2
x = a.index(doubled)
y = a_r.index(doubled)
num = x + y

print(n)

for i in range(2, n + 2):
	if num >= i - 1:
		print(int((comb(n + 1, i) - comb(num, i - 1)) % MOD))
	else:
		print(comb(n + 1, i))

Submission status: Runtime Error

Solution code:
MOD = (10 ** 9) + 7

f_list = [1] * 100000
f_r_list = [1] * 100000

for i in range(99999):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, 100001):
	f_r_list[-i] = int((f_r_list[-i + 1] * (100002 - i)) % MOD)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

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


doubled = sum(a) - n * (n + 1) / 2
x = a.index(doubled)
y = a_r.index(doubled)
num = x + y

print(n)

for i in range(2, n + 2):
	if num >= i - 1:
		print(int((comb(n + 1, i) - comb(num, i - 1)) % MOD))
	else:
		print(comb(n + 1, i))

Submission status: Runtime Error

Solution code:
MOD = (10 ** 9) + 7

f_list = [1] * 100000
f_r_list = [1] * 100000

for i in range(99999):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, 100001):
	f_r_list[-i] = int((f_r_list[-i + 1] * (100002 - i)) % MOD)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

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


doubled = sum(a) - n * (n + 1) / 2
x = a.index(doubled)
y = a_r.index(doubled)
num = x + y

print(n)

for i in range(2, n + 2):
	if num >= i - 1:
		print(comb(n + 1, i) - comb(num, i - 1))
	else:
		print(comb(n + 1, i))

Submission status: Runtime Error

Solution code:
from statistics import mode

n=int(input())
a=[int(i) for i in input().split()]
d=mode(a)

x=0
lr=0
for i in a:
  if i==d:
    x+=1
  if x==0 or x==2:
    lr+=1
lr-=1    
b=1
c=1
for i in range(n+1):
  b *= n + 1 - i
  b /= i + 1
  m=0

  if i==0:
    m+=1
  elif lr + 1 -i>=0:
    c *= lr + 1 -i
    c /= i 
    m+=int(c)
  print((int(b) - m )% (10**9 + 7) )

Submission status: Runtime Error

Solution code:
from statistics import mode

n=int(input())
a=[int(i) for i in input().split()]
d=mode(a)

x=0
lr=0
for i in a:
  if i==d:
    x+=1
  if x==0 or x==2:
    lr+=1
lr-=1    
bb=1
bs=1
cb=1
cs=1
for i in range(n+1):
  bb *= (n + 1 - i)
  bs *= (i + 1)
  m=0

  if i==0:
    m+=1
  elif lr + 1 -i>=0:
    cb *= (lr + 1 -i)
    cs *= (i )
    m+=int(cb/cs)
  print((int(bb/bs) - m )% (10**9 + 7) )

Submission status: Runtime Error

Solution code:
from statistics import mode

n=int(input())
a=[int(i) for i in input().split()]
d=mode(a)

x=0
lr=0
for i in a:
  if i==d:
    x+=1
  if x==0 or x==2:
    lr+=1
lr-=1    
bb=1
bs=1
cb=1
cs=1
for i in range(n+1):
  bb *= (n + 1 - i)
  bs *= (i + 1)
  m=0

  if i==0:
    m+=1
  else:
    cb *= (lr + 1 -i)
    cs *= (i )
    m+=int(cb/cs)
  print((int(bb/bs) - m )% (10**9 + 7) )

Submission status: Runtime Error

Solution code:
# https://arc077.contest.atcoder.jp/tasks/arc077_b

MOD = 10**9 + 7

from itertools import accumulate

F = [1] + list(accumulate(range(1, 10001), lambda x, y:x * y % MOD))

def C(n, r, cache={}):
    if (n, r) in cache:
        return cache[n, r]
    result = F[n] * pow(F[r], MOD - 2, MOD) * pow(F[n - r], MOD - 2, MOD) % MOD
    cache[n, r] = result
    return result

def solve(N, L, M):
    for i in range(1, 1 + N + L + M):
        result = 0
        for n in range(min(N + 1, i + 1)):
            cn = C(N, n)
            for m in range(min(M + 1, i - n + 1)):
                l = i - m - n
                if 0 <= l <= L:
                    cl = C(L, l)
                    if l == 1:
                        cl -= 1
                    c = cn * cl * C(M, m)
                    result = (result + c) % MOD
        print(result)

n = int(input())
A = [int(_) for _ in input().split()]
pos = {}

for i, a in enumerate(A):
    if a in pos:
        N = pos[a]
        M = n - i
        L = n - N - M + 1
    else:
        pos[a] = i

solve(N, L, M)

Submission status: Runtime Error

Solution code:
# https://arc077.contest.atcoder.jp/tasks/arc077_b

MOD = 10**9 + 7

from itertools import accumulate

F = [1] + list(accumulate(range(1, 10000), lambda x, y:x * y % MOD))

def C(n, r, cache={}):
    if (n, r) in cache:
        return cache[n, r]
    result = F[n] * pow(F[r], MOD - 2, MOD) * pow(F[n - r], MOD - 2, MOD) % MOD
    cache[n, r] = result
    return result

def solve(N, L, M):
    for i in range(1, 1 + N + L + M):
        result = 0
        for n in range(min(N + 1, i + 1)):
            cn = C(N, n)
            for m in range(min(M + 1, i - n + 1)):
                l = i - m - n
                if l <= L:
                    cl = C(L, l)
                    if l == 1:
                        cl -= 1
                    c = cn * cl * C(M, m)
                    result = (result + c) % MOD
        print(result)

n = int(input())
A = [int(_) for _ in input().split()]
pos = {}

for i, a in enumerate(A):
    if a in pos:
        N = pos[a]
        M = n - i
        L = n - N - M + 1
    else:
        pos[a] = i

solve(N, L, M)

Submission status: Runtime Error

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

def binary_exp_with_mod(x,n,mod):
  p = x
  ret = 1
  while n > 0:
    if n % 2 == 0:
      p = (p * p) % mod
      n /= 2
    else:
      ret = (ret * p) % mod
      n -= 1
  return ret

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

BP = 10**9+7

x = -1
j = -1
s = set()
for i in range(n+1):
  if a[i] in s:
    x = a[i]
    j = i
    break
  else:
    s.add(a[i])

k = a.index(a[j])

N = n + 1
nck = {(N,0): 1}
for i in range(N / 2 + 2):
  nck[(N,i+1)] = (nck[(N,i)] * (N-i) * binary_exp_with_mod(i+1, BP-2, BP)) % BP

M = N - (j - k + 1)
mck = {(M,0): 1}
for i in range(M / 2 + 2):
  mck[(M,i+1)] = (mck[(M,i)] * (M-i) * binary_exp_with_mod(i+1, BP-2, BP)) % BP

print n
for i in range(2,N+1):
  if i-1 > M:
    i = min(i, N-i)
    print nck[(N,i)]
  else:
    print nck[(N,i)] - mck[(M,i-1)]

Submission status: Runtime Error

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

def binary_exp_with_mod(x,n,mod):
  p = x
  ret = 1
  while n > 0:
    if n % 2 == 0:
      p = (p * p) % mod
      n /= 2
    else:
      ret = (ret * p) % mod
      n -= 1
  return ret

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

BP = 10**9+7

x = -1
j = -1
s = set()
for i in range(n+1):
  if a[i] in s:
    x = a[i]
    j = i
    break
  else:
    s.add(a[i])

k = a.index(a[j])

N = n + 1
nck = {(N,0): 1}
for i in range(N / 2 + 2):
  nck[(N,i+1)] = (nck[(N,i)] * (N-i) * binary_exp_with_mod(i+1, BP-2, BP)) % BP

print j,N

M = N - (j - k + 1)
mck = {(M,0): 1}
for i in range(M / 2 + 2):
  mck[(M,i+1)] = (mck[(M,i)] * (M-i) * binary_exp_with_mod(i+1, BP-2, BP)) % BP

print n
for i in range(2,N+1):
  if i-1 > M:
    i = min(i, N-i)
    print nck[(N,i)]
  else:
    print nck[(N,i)] - mck[(M,i-1)]

Submission status: Runtime Error

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

def binary_exp_with_mod(x,n,mod):
  p = x
  ret = 1
  while n > 0:
    if n % 2 == 0:
      p = (p * p) % mod
      n /= 2
    else:
      ret = (ret * p) % mod
      n -= 1
  return ret

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

BP = 10**9+7

x = -1
j = -1
s = set()
for i in range(n+1):
  if a[i] in s:
    x = a[i]
    j = i
    break
  else:
    s.add(a[i])

b = a[:i] + a[i+1:]

N = n + 1
nck = {(N,0): 1}
# i > N/2以上のときは、nckが小さくなっていくので、そのままmod BPを計算してはいけない
for i in range(N / 2 + 2):
  nck[(N,i+1)] = (nck[(N,i)] * (N-i) * binary_exp_with_mod(i+1, BP-2, BP)) % BP

NJ = N-j
njck = {(NJ,0): 1}
for i in range(NJ / 2 + 2):
  njck[(NJ,i+1)] = (njck[(NJ,i)] * (NJ-i) * binary_exp_with_mod(i+1, BP-2, BP)) % BP

print n
for i in range(2,N+1):
  if i > N-j:
    i = min(i, N-i)
    print nck[(N,i)]
  else:
    #  i would be graeter than (N-j)/2
    print (nck[(N,i)] - njck[(N-j,i)])

Submission status: Runtime Error

Solution code:
from collections import Counter

n=int(input())
s=[int(i) for i in input().split()]
div=int(10**9+7)
c = Counter(s)
j=-1
for i in range(1, n + 1):
    if c[i] == 2:
        j = i
        break
a, b = [i for i in range(n + 1) if s[i] == j]

f=[1]
t=1
for i in range(1,n+2):
    t=t*i
    f.append(t)


for i in range(1,n+2):
    x=round(f[n+1]/(f[i]*f[n+1-i]))
    y=round(f[a+n-b]/(f[i-1]*f[a+n-b-i+1]))
    ans=(x-y)%div
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100001)


def get_ncr(div):
    cache = {}

    def f(*args):
        if args in cache:
            return cache[args]
        n, r = args
        if r == 0 or n == r:
            cache[args] = 1
            return 1
        cache[args] = (f(n - 1, r) + f(n - 1, r - 1)) % div
        return cache[args]

    return f


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


n = int(input())
aa = list(map(int, input().split()))
i1, i2 = find_duplicated(aa)
between_n = i2 - i1 + 1
outside_n = n + 1 - between_n
div = int(1e9 + 7)
ncr = get_ncr(div)

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

Solution code:
import sys

sys.setrecursionlimit(100000)


def get_ncr(div):
    cache = {}

    def f(*args):
        if args in cache:
            return cache[args]
        n, r = args
        if r == 0 or n == r:
            cache[args] = 1
            return 1
        cache[args] = (f(n - 1, r) + f(n - 1, r - 1)) % div
        return cache[args]

    return f


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


n = int(input())
aa = list(map(int, input().split()))
i1, i2 = find_duplicated(aa)
between_n = i2 - i1 + 1
outside_n = n + 1 - between_n
div = int(1e9 + 7)
ncr = get_ncr(div)

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

Solution code:
import sys

sys.setrecursionlimit(100000)


def get_ncr():
    cache = {}

    def f(*args):
        if args in cache:
            return cache[args]
        n, r = args
        if r == 0 or n == r:
            cache[args] = 1
            return 1
        cache[args] = f(n - 1, r) + f(n - 1, r - 1)
        return cache[args]

    return f


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


n = int(input())
aa = list(map(int, input().split()))
i1, i2 = find_duplicated(aa)
pre_n = i1
mid_n = i2 - i1 + 1
post_n = n + 1 - i2 - 1
ncr = get_ncr()
div = int(1e9 + 7)

for total in range(1, n + 2):
    ans = 0
    for i in range(max(total - pre_n - post_n, 0), min(total, mid_n) + 1):
        if i == 1:
            ic = mid_n - 1
        else:
            ic = ncr(mid_n, i)
        for j in range(max(total - i - post_n, 0), min(total - i, pre_n) + 1):
            k = total - i - j
            ans = (ans + ic * ncr(pre_n, j) * ncr(post_n, k)) % div
    print(ans)

Submission status: Runtime Error

Solution code:
def get_ncr():
    cache = {}

    def f(*args):
        if args in cache:
            return cache[args]
        n, r = args
        if r == 0 or n == r:
            cache[args] = 1
            return 1
        cache[args] = f(n - 1, r) + f(n - 1, r - 1)
        return cache[args]

    return f


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


n = int(input())
aa = list(map(int, input().split()))
i1, i2 = find_duplicated(aa)
pre_n = i1
mid_n = i2 - i1 + 1
post_n = n + 1 - i2 - 1
ncr = get_ncr()
div = int(1e9 + 7)

for total in range(1, n + 2):
    ans = 0
    for i in range(max(total - pre_n - post_n, 0), min(total, mid_n) + 1):
        if i == 1:
            ic = mid_n - 1
        else:
            ic = ncr(mid_n, i)
        for j in range(max(total - i - post_n, 0), min(total - i, pre_n) + 1):
            k = total - i - j
            ans = (ans + ic * ncr(pre_n, j) * ncr(post_n, k)) % div
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
seq = input().split()
lc = 'a'
already = []
for idx,c in enumerate(seq):
    if c in already:
        break
    already.append(c)
    lc = c

left = seq.index(c)
right = list(reversed(seq)).index(c)
middle = n-left-right-2
# print(left,middle,right,lc)
# print(seq)
NUM = 10**9+7

# def f(n):
#     if n<=1:
#         return 1
#     else:
#         return n*f(n-1)
#
from math import factorial
def f(n,k):
    if n<k:
        return 1
    else:
        return n*f(n-1,k)


def c(n,k):
    if k == 1:
        return n
    if k == n:
        return 1
    # return f(n)//(f(k) * f(n-k))
    return f(n,k+1)//f(n-k,1)

def calc(n,k):
    if k == 1:
        return n-1
    if k == n:
        return 1
    # if k == n-1:
    #     return c(n,k) - 1
    # if k == 2:
    #     return c(n,k) - lidx - (n-ridx)
    # if k == 3:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,1)
    # if k == 4:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,2) - c(lidx,2) * c(n-ridx,1)
    if k-1 > left+right:
        return c(n,k)
    else:
        return c(n,k) - c(left+right, k-1)


for k in range(1,n+1 +1):
    print(int(calc(n+1,k))%NUM)

Submission status: Runtime Error

Solution code:
n = int(input())
seq = input().split()
lc = 'a'
already = []
for idx,c in enumerate(seq):
    if c in already:
        break
    already.append(c)
    lc = c

left = seq.index(c)
right = list(reversed(seq)).index(c)
middle = n-left-right-2
# print(left,middle,right,lc)
# print(seq)
NUM = 10**9+7

# def f(n):
#     if n<=1:
#         return 1
#     else:
#         return n*f(n-1)
#
from math import factorial
def f(n,k):
    if n<=k:
        return n
    else:
        return n*f(n-1,k)


def c(n,k):
    if k == 1:
        return n
    if k == n:
        return 1
    # return f(n)//(f(k) * f(n-k))
    return f(n,k+1)//f(n-k,1)

def calc(n,k):
    if k == 1:
        return n-1
    if k == n:
        return 1
    # if k == n-1:
    #     return c(n,k) - 1
    # if k == 2:
    #     return c(n,k) - lidx - (n-ridx)
    # if k == 3:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,1)
    # if k == 4:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,2) - c(lidx,2) * c(n-ridx,1)
    if k-1 > left+right:
        return c(n,k)
    else:
        return c(n,k) - c(left+right, k-1)


for k in range(1,n+1 +1):
    print(int(calc(n+1,k))%NUM)

Submission status: Runtime Error

Solution code:
n = int(input())
seq = input().split()
lc = 'a'
already = []
for idx,c in enumerate(seq):
    if c in already:
        break
    already.append(c)
    lc = c

left = seq.index(c)
right = list(reversed(seq)).index(c)
middle = n-left-right-2
# print(left,middle,right,lc)
# print(seq)
NUM = 10**9+7

# def f(n):
#     if n<=1:
#         return 1
#     else:
#         return n*f(n-1)
#
from math import factorial
def f(n,k):
    if n<=k:
        return n
    else:
        return n*f(n-1,k)


def c(n,k):
    if k == 1:
        return n
    if k == n:
        return 1
    # return f(n)//(f(k) * f(n-k))
    return f(n,k+1)//f(n-1,1)

def calc(n,k):
    if k == 1:
        return n-1
    if k == n:
        return 1
    # if k == n-1:
    #     return c(n,k) - 1
    # if k == 2:
    #     return c(n,k) - lidx - (n-ridx)
    # if k == 3:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,1)
    # if k == 4:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,2) - c(lidx,2) * c(n-ridx,1)
    if k-1 > left+right:
        return c(n,k)
    else:
        return c(n,k) - c(left+right, k-1)


for k in range(1,n+1 +1):
    print(int(calc(n+1,k))%NUM)

Submission status: Runtime Error

Solution code:
n = int(input())
seq = input().split()
lc = 'a'
already = []
for idx,c in enumerate(seq):
    if c in already:
        break
    already.append(c)
    lc = c

left = seq.index(c)
right = list(reversed(seq)).index(c)
middle = n-left-right-2
# print(left,middle,right,lc)
# print(seq)
NUM = 10**9+7

def f(n):
    if n<=1:
        return 1
    else:
        return n*f(n-1)

def c(n,k):
    if k == 1:
        return n
    if k == n:
        return 1
    return (f(n)/(f(k) * f(n-k))%NUM)

def calc(n,k):
    if k == 1:
        return n-1
    if k == n:
        return 1
    # if k == n-1:
    #     return c(n,k) - 1
    # if k == 2:
    #     return c(n,k) - lidx - (n-ridx)
    # if k == 3:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,1)
    # if k == 4:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,2) - c(lidx,2) * c(n-ridx,1)
    if k-1 > left+right:
        return c(n,k)
    else:
        return c(n,k) - c(left+right, k-1)


for k in range(1,n+1 +1):
    print(int(calc(n+1,k))%NUM)

Submission status: Runtime Error

Solution code:
n = int(input())
seq = input().split()
lc = 'a'
already = []
for idx,c in enumerate(seq):
    if c in already:
        break
    already.append(c)
    lc = c

left = seq.index(c)
right = list(reversed(seq)).index(c)
middle = n-left-right-2
# print(left,middle,right,lc)
# print(seq)
NUM = 10**9+7

def f(n):
    if n<=1:
        return 1
    else:
        return n*f(n-1)

def c(n,k):
    if k == 1:
        return n
    # if k == n:
    #     return 1
    return (f(n)/(f(k) * f(n-k))%NUM)

def calc(n,k):
    if k == 1:
        return n-1
    if k == n:
        return 1
    # if k == n-1:
    #     return c(n,k) - 1
    # if k == 2:
    #     return c(n,k) - lidx - (n-ridx)
    # if k == 3:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,1)
    # if k == 4:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,2) - c(lidx,2) * c(n-ridx,1)
    if k-1 > left+right:
        return c(n,k)
    else:
        return c(n,k) - c(left+right, k-1)


for k in range(1,n+1 +1):
    print(int(calc(n+1,k))%NUM)

Submission status: Runtime Error

Solution code:
n = int(input())
seq = input().split()
lc = 'a'
already = []
for idx,c in enumerate(seq):
    if c in already:
        break
    already.append(c)
    lc = c

left = seq.index(c)
right = list(reversed(seq)).index(c)
middle = n-left-right-2
# print(left,middle,right,lc)
# print(seq)

def f(n):
    if n<=1:
        return 1
    else:
        return n*f(n-1)

def c(n,k):
    if k == 1:
        return n
    # if k == n:
    #     return 1
    return f(n)/(f(k) * f(n-k))

def calc(n,k):
    if k == 1:
        return n-1
    if k == n:
        return 1
    # if k == n-1:
    #     return c(n,k) - 1
    # if k == 2:
    #     return c(n,k) - lidx - (n-ridx)
    # if k == 3:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,1)
    # if k == 4:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,2) - c(lidx,2) * c(n-ridx,1)
    if k-1 > left+right:
        return c(n,k)
    else:
        return c(n,k) - c(left+right, k-1)

NUM = 10**9+7

for k in range(1,n+1 +1):
    print(int(calc(n+1,k))%NUM)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

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

def com(n, k):
    if n == 0 or k == 0:
        return 1
    return int(reduce(mul, range(n + 1 - k, n + 1)) / reduce(mul, range(1, k + 1))) % (10 ** 9 + 7)

idx_list = [-1] * (n + 2)
l = 0
r = 0
for i, a_i in enumerate(a):
    if idx_list[a_i] < 0:
        idx_list[a_i] = i
    else:
        l = idx_list[a_i]
        r = n - i
        break

for k in range(1, n + 2):
    m = k - 1
    dup = 0
    for l_n in range(0, m + 1):
        r_n = m - l_n
        if l_n > l or r_n > r:
            continue
        l_c = com(l, l_n)
        r_c = com(r, r_n)
        dup += l_c * r_c
    ans = (com(n + 1, k) - dup) % (10 ** 9 + 7)
    print(ans)