Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has a sequence of integers $A_{1}, A_{2}, \ldots, A_{N}$. He takes a sheet of paper and for each non-empty subsequence $B$ of this sequence, he does the following:
1. For each integer which appears in $B$, count its number of occurrences in the sequence $B$.
2. Choose the integer with the largest number of occurrences. If there are several options, choose the smallest one.
3. Finally, write down the chosen integer (an element of $B$) on the sheet of paper.

For each integer between $1$ and $N$ inclusive, find out how many times it appears on Chef's sheet of paper. Since these numbers may be very large, compute them modulo $1,000,000,007$ ($10^{9} + 7$).

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing $N$ space-separated integers. For each valid $i$, the $i$-th of these integers should be the number of occurrences of $i$ on Chef's sheet of paper.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ A_{i} ≤ N$ for each valid $i$
the sum of $N$ over all test cases does not exceed $500,000$

------  Subtasks ------
Subtask #1 (20 points): the sum of $N$ over all test cases does not exceed $5,000$

Subtask #2 (10 points): $A_{1}, A_{2}, \ldots, A_{N}$ is a permutation of the integers $1$ through $N$

Subtask #3 (70 points): original constraints

----- Sample Input 1 ------ 
3

3

2 2 3

2

1 2

3

1 2 2
----- Sample Output 1 ------ 
0 6 1

2 1

3 4 0
----- explanation 1 ------ 
Example case 3: There are $7$ non-empty subsequences:
- $[1]$ (Chef writes down $1$)
- $[2]$ (Chef writes down $2$)
- $[2]$ (Chef writes down $2$)
- $[1, 2]$ (Chef writes down $1$)
- $[1, 2]$ (Chef writes down $1$)
- $[2, 2]$ (Chef writes down $2$)
- $[1, 2, 2]$ (Chef writes down $2$)

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Combinatorics

Greedy algorithms

Dynamic programming

Mathematics

Data structures


Solutions:
import sys
from collections import deque
mod = 10 ** 9 + 7

def invert(k):
	return pow(k, mod - 2, mod)
fact = [1] * 500001
ifact = [1] * 500001
for i in range(2, 500001):
	fact[i] = i * fact[i - 1]
	ifact[i] = invert(i) * ifact[i - 1]
	fact[i] %= mod
	ifact[i] %= mod

def ncr(k, l):
	return fact[k] * ifact[l] % mod * ifact[k - l] % mod
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	st = list(d.keys())
	st.sort(reverse=True)
	sum_till_now = [0] * (n + 1)
	final_count = [0] * (n + 1)
	times = [0] * (n + 1)
	for i in st:
		sum_till_now[i] = 1
	st_length = len(st)
	st = deque(st)
	ans = 1
	while st_length > 0:
		b = st.popleft()
		st_length -= 1
		x = ncr(d[b], times[b] + 1)
		ans *= invert(sum_till_now[b])
		ans %= mod
		sum_till_now[b] += x
		sum_till_now[b] %= mod
		final_count[b] += ans * x
		final_count[b] %= mod
		ans *= sum_till_now[b]
		ans %= mod
		times[b] += 1
		if times[b] != d[b]:
			st.append(b)
			st_length += 1
	print(*final_count[1:])


N = 1000001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def ncr(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans

def addMod(a, b):
	mod = 10 ** 9 + 7
	return (a % mod + b % mod) % mod

def multiMod(a, b):
	mod = 10 ** 9 + 7
	return a % mod * (b % mod) % mod
p = 1000000007
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = {}
	a = sorted(a)
	maxFreq = -1
	for i in a:
		if i not in f:
			f[i] = 1
		else:
			f[i] += 1
		maxFreq = max(maxFreq, f[i])
	distict = []
	for i in f:
		distict.append(i)
	distict = sorted(distict)
	ncrPRE = {}
	for number in distict:
		temp = [1]
		for rep in range(1, f[number] + 1):
			temp.append(addMod(ncr(f[number], rep, p), temp[-1]))
		ncrPRE[number] = temp
	ans = {}
	for i in range(1, n + 1):
		ans[i] = 0
	tempAns = {}
	extraFactorRight = {}
	for i in distict:
		extraFactorRight[i] = 1
	extraFactorLeft = {}
	for i in distict:
		extraFactorLeft[i] = 1
	distictBackWards = distict[::-1]
	for possibleFreq in range(1, maxFreq + 1):
		temp = ncrPRE[distictBackWards[0]][possibleFreq]
		tempAns[distictBackWards[0]] = multiMod(ncr(f[distictBackWards[0]], possibleFreq, p), extraFactorLeft[distictBackWards[0]])
		for number in distictBackWards[1:]:
			tempAns[number] = 1
			tempAns[number] = multiMod(tempAns[number], ncr(f[number], possibleFreq, p))
			tempAns[number] = multiMod(tempAns[number], temp)
			tempAns[number] = multiMod(tempAns[number], extraFactorLeft[number])
			temp = multiMod(temp, ncrPRE[number][possibleFreq])
		temp = ncrPRE[distict[0]][possibleFreq - 1]
		tempAns[distict[0]] = multiMod(tempAns[distict[0]], extraFactorRight[distict[0]])
		for number in distict[1:]:
			tempAns[number] = multiMod(tempAns[number], temp)
			tempAns[number] = multiMod(tempAns[number], extraFactorRight[number])
			temp = multiMod(temp, ncrPRE[number][possibleFreq - 1])
		for i in distict:
			ans[i] = addMod(tempAns[i], ans[i])
		tempHadHogi = []
		for i in distict:
			if f[i] == possibleFreq:
				extraFactorRight[i] = ncrPRE[i][-1]
				extraFactorLeft[i] = ncrPRE[i][-1]
				tempHadHogi.append(ncrPRE[i][-1])
			else:
				tempHadHogi.append(1)
		preHadHogi = [tempHadHogi[0]]
		for ii in range(1, len(distict)):
			preHadHogi.append(multiMod(preHadHogi[-1], tempHadHogi[ii]))
		postHadHogi = [tempHadHogi[len(distict) - 1]]
		for ii in range(len(tempHadHogi) - 2, -1, -1):
			postHadHogi.append(multiMod(postHadHogi[-1], tempHadHogi[ii]))
		postHadHogi = postHadHogi[::-1]
		for ii in range(len(distict)):
			extraFactorLeft[distict[ii]] = multiMod(extraFactorLeft[distict[ii]], postHadHogi[ii])
		for ii in range(len(distict)):
			extraFactorRight[distict[ii]] = multiMod(extraFactorRight[distict[ii]], preHadHogi[ii])
		delIndex = []
		for i in range(len(distict)):
			if f[distict[i]] == possibleFreq:
				delIndex.append(i)
		delIndex = delIndex[::-1]
		for i in delIndex:
			del distict[i]
		distictBackWards = distict[::-1]
	for i in range(1, n + 1):
		print(ans[i], end=' ')
	print('')


def mul(a, b, c):
	for i in range(min(len(a), len(b))):
		a[i] = a[i] * b[i] % 1000000007
	for i in range(len(a), len(b)):
		a.append(b[i])
	return a[:c]

def preProcess():
	fac = [1, 1]
	for i in range(2, 500001):
		fac.append(i * fac[i - 1] % 1000000007)
	return fac

def solve(n, arr, fac, modInverse):
	m = 1000000007
	ans = [0] * n
	cntArr = [0] * (n + 1)
	for i in arr:
		cntArr[i] += 1
	nArr = []
	for i in cntArr:
		if i == 0:
			continue
		nArr.append(i)
	lessC = [0 for _ in range(max(nArr) + 1)]
	for i in nArr:
		lessC[i] += 1
	for i in range(len(lessC)):
		lessC[i] = i * lessC[i]
	for i in range(1, len(lessC)):
		lessC[i] = lessC[i - 1] + lessC[i]
	for i in range(len(lessC)):
		lessC[i] = pow(2, lessC[i], m)
	ncr = [[] for _ in range(len(nArr))]
	for i in range(len(nArr)):
		for j in range(nArr[i] + 1):
			modInverse[j] = modInverse[j] if modInverse[j] else pow(fac[j], m - 2, m)
			modInverse[nArr[i] - j] = modInverse[nArr[i] - j] if modInverse[nArr[i] - j] else pow(fac[nArr[i] - j], m - 2, m)
			ncr[i].append(fac[nArr[i]] * modInverse[j] * modInverse[nArr[i] - j] % m)
	preArr = [[1] for _ in range(len(nArr))]
	for i in range(len(ncr)):
		for j in range(1, len(ncr[i])):
			preArr[i].append(preArr[i][j - 1] + ncr[i][j] if j < len(ncr[i]) else preArr[i][j - 1])
	nArrL = [False for _ in range(len(nArr))]
	nArrR = [False for _ in range(len(nArr))]
	currL = []
	currR = []
	for i in range(1, len(preArr)):
		nArrL[i] = mul(currL, preArr[i - 1][:-1], len(preArr[i]))
		nArrR[-1 - i] = mul(currR, preArr[-i], len(preArr[-1 - i]))
	cArr = []
	for i in range(len(ncr)):
		sm = 0
		for j in range(1, len(ncr[i])):
			pro = ncr[i][j]
			if nArrL[i] is not False and j - 1 < len(nArrL[i]):
				pro = pro * nArrL[i][j - 1] % m
			if nArrR[i] is not False and j < len(nArrR[i]):
				pro = pro * nArrR[i][j] % m
			pro = pro * lessC[j - 1] % m
			sm = (sm + pro) % m
		cArr.append(sm)
	ans = []
	j = 0
	for i in cntArr[1:]:
		if i == 0:
			ans.append(0)
		else:
			ans.append(cArr[j])
			j += 1
	print(' '.join(list(map(str, ans))))

def main():
	fac = preProcess()
	modInv = [False for _ in range(len(fac))]
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		solve(n, arr, fac, modInv)
main()


from collections import Counter

def main():
	MOD = 1000000007
	f = [0] * 500005

	def nCr(n, r):
		if r == 0:
			return 1
		else:
			return f[n] * pow(f[n - r], MOD - 2, MOD) % MOD * pow(f[r], MOD - 2, MOD) % MOD

	def solve():
		f[0] = 1
		f[1] = 1
		for i in range(2, 500005):
			f[i] = f[i - 1] * i % MOD
		_ = int(input())
		for __ in range(_):
			n = int(input())
			arr = list(map(int, input().split()))
			hashMap = dict(Counter(arr))
			k = [0] * (n + 3)
			u = [0] * (n + 2)
			for i in range(n + 2):
				k[i] = 1
				u[i] = 1
			for (key, value) in hashMap.items():
				s = 1
				for j in range(1, value + 1):
					s += nCr(value, j)
					s %= MOD
					k[j] *= s
					k[j] %= MOD
				u[value + 1] *= s
				u[value + 1] %= MOD
			m = 1
			for i in range(1, n + 1):
				m *= u[i]
				m %= MOD
				k[i] *= m
				k[i] %= MOD
			for i in range(1, n + 1):
				a = 0
				ta = 0
				s = 1
				if i in hashMap:
					for j in range(1, hashMap[i] + 1):
						ta = nCr(hashMap[i], j)
						tmp = ta
						s += ta
						s %= MOD
						k[j] = k[j] * pow(s, MOD - 2, MOD) % MOD
						ta *= k[j]
						ta %= MOD
						k[j] = k[j] * (s - tmp + MOD) % MOD % MOD
						a += ta
						a %= MOD
				print(a % MOD, end=' ')
			print()
	solve()
main()


import math
import sys
from collections import defaultdict, Counter, deque
input = sys.stdin.readline

def rais(a, b, c):
	num = 0
	if b == 0:
		return 1
	x = rais(a, b // 2, c) % c
	x = x * x % c
	if b % 2 == 0:
		return x
	else:
		return a * x % c
test = int(input())
mod = int(pow(10, 9)) + 7
for num in range(test):
	n = int(input())
	a = list(map(int, input().split()))
	fset = {}
	dat = 0
	maxf = 1
	for k in range(1, n + 1):
		fset[a[k - 1]] = fset.get(a[k - 1], 0) + 1
		maxf = max(maxf, fset[a[k - 1]])
	if maxf == 1:
		for j in range(1, n + 1):
			print(pow(2, n - j, mod), end=' ')
		print()
		continue
	while False:
		break
	fset = sorted(fset.items())
	fset2 = len(fset)
	left = {}
	right = {}
	for k in range(fset2):
		right[fset[k][1]] = right.get(fset[k][1], 0) + 1
	factoril = list()
	factoril.append(1)
	opp = list()
	opp.append(1)
	for j in range(1, maxf + 1):
		factoril.append(factoril[j - 1] * j % mod)
		opp.append(pow(factoril[j], mod - 2, mod))
	while False:
		break
	mul = defaultdict(list)
	for j in right:
		mul[j].append(opp[j])
		for k in range(1, j + 1):
			mul[j].append(mul[j][k - 1])
			mul[j][k] = (mul[j][k] + opp[k] * opp[j - k] % mod) % mod
	if n * len(right) < maxf * fset2:
		listans = [0] * (n + 1)
		for j in range(fset2):
			right[fset[j][1]] -= 1
			p = 1
			while False:
				break
			while p <= fset[j][1]:
				curr = factoril[fset[j][1]] * (opp[p] * opp[fset[j][1] - p]) % mod % mod
				for k in right:
					dat = 0
					curr = curr * pow(factoril[k] * mul[k][min(p, k)] % mod, right[k], mod) % mod
				for k in left:
					curr = curr * pow(factoril[k] * mul[k][min(p - 1, k)] % mod, left[k], mod) % mod
				listans[fset[j][0]] = (listans[fset[j][0]] + curr) % mod
				p += 1
			left[fset[j][1]] = left.get(fset[j][1], 0) + 1
		print(*listans[1:])
		continue
	dat = 0
	ans1 = defaultdict(list)
	ans2 = defaultdict(deque)
	for j in range(maxf + 1):
		ans1[j].append(mul[fset[0][1]][min(j, fset[0][1])])
		for k in range(1, fset2):
			ans1[j].append(ans1[j][k - 1])
			ans1[j][k] = ans1[j][k] * mul[fset[k][1]][min(j, fset[k][1])] % mod
		ans1[j].append(1)
		while False:
			break
		ans2[j].append(1)
		ans2[j].appendleft(mul[fset[-1][1]][min(j, fset[-1][1])])
		for k in range(fset2 - 2, -1, -1):
			ans2[j].appendleft(ans2[j][0])
			ans2[j][0] = ans2[j][0] * mul[fset[k][1]][min(j, fset[k][1])] % mod
	listans = [0] * (n + 1)
	eve = 1
	for j in range(fset2):
		eve = eve * factoril[fset[j][1]] % mod
		p = 1
		while p <= fset[j][1]:
			while False:
				break
			val = opp[p] * opp[fset[j][1] - p] % mod
			val = val * ans2[p][j + 1] % mod * ans1[p - 1][j - 1] % mod
			dat = 0
			listans[fset[j][0]] = (listans[fset[j][0]] + val) % mod
			p += 1
	for j in range(1, n + 1):
		print(eve * listans[j] % mod, end=' ')
	print()


data_ad = {}

def ncr(n, data_ad):
	arr = [1]
	num = den = 1
	for i in range(n // 2):
		num = num * (n - i) % 1000000007
		den = den * (i + 1) % 1000000007
		if den not in data_ad:
			data_ad[den] = pow(den, 1000000005, 1000000007)
		arr.append(num * data_ad[den] % 1000000007)
	return arr
data_com = {}
for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	l.sort(reverse=True)
	ques = []
	last = l[0]
	cnt = 0
	ini_count_2 = {}
	com = {}
	ad = {}
	count = {}
	for j in range(len(l)):
		if l[j] == last:
			cnt += 1
			if len(ques) >= cnt:
				ques[cnt - 1].append(l[j])
			else:
				ques.append([l[j]])
		else:
			if cnt not in data_com:
				data_com[cnt] = ncr(cnt, data_ad)
			cnt = 1
			last = l[j]
			if len(ques) >= cnt:
				ques[cnt - 1].append(l[j])
			else:
				ques.append([l[j]])
		if l[j] not in ad:
			count[l[j]] = 1
			ad[l[j]] = 1
			ini_count_2[l[j]] = 0
		else:
			count[l[j]] += 1
	if cnt not in data_com:
		data_com[cnt] = ncr(cnt, data_ad)
	ans = []
	mul = 1
	mu_1 = 1
	for j in range(len(l)):
		ans.append(0)
	for i in range(len(ques)):
		for j in range(len(ques[i])):
			temp = ques[i][j]
			ind = ini_count_2[temp]
			if ad[temp] not in data_ad:
				data_ad[ad[temp]] = pow(ad[temp], 1000000005, 1000000007)
				mul = mul * data_ad[ad[temp]] % 1000000007
			else:
				mul = mul * data_ad[ad[temp]] % 1000000007
			mul_1 = mul
			if count[temp] // 2 >= ind + 1:
				ad[temp] = (ad[temp] + data_com[count[temp]][ind + 1]) % 1000000007
				mul_1 = mul_1 * data_com[count[temp]][ind + 1] % 1000000007
			else:
				ad[temp] = (ad[temp] + data_com[count[temp]][count[temp] - (ind + 1)]) % 1000000007
				mul_1 = mul_1 * data_com[count[temp]][count[temp] - (ind + 1)] % 1000000007
			mul = mul * ad[temp] % 1000000007
			ans[temp - 1] = (ans[temp - 1] + mul_1) % 1000000007
			ini_count_2[temp] += 1
	print(*ans)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	dic = {}
	maxg = 0
	for i in range(N):
		if A[i] in dic:
			dic[A[i]] += 1
		else:
			dic[A[i]] = 1
		maxg = max(maxg, dic[A[i]])
	if len(dic.keys()) == 1:
		x = pow(2, N, mod) - 1
		j = A[0]
		for i in range(N):
			if i == A[0] - 1:
				print(x, end=' ')
			else:
				print(0, end=' ')
	else:
		length = [0 for i in range(maxg)]
		for i in dic.keys():
			for j in range(dic[i]):
				length[j] += 1
		index_length = [0 for i in range(maxg)]
		precompute = [[0 for j in range(length[i])] for i in range(maxg)]
		y = [0 for i in range(len(dic.keys()))]
		io = 0
		for i in range(1, N + 1):
			if i in dic:
				y[io] = i
				io += 1
		NCRsum = [[] for i in range(N + 1)]
		precomputetill = [[] for i in range(N + 1)]
		ifdone = [False for i in range(N + 1)]
		ifdonepos = [0 for i in range(N + 1)]
		for i in y:
			w = dic[i]
			if ifdone[w]:
				NCRsum[i] = NCRsum[ifdonepos[w]].copy()
				precomputetill[i] = precomputetill[ifdonepos[w]].copy()
				for j in range(w):
					precompute[j][index_length[j]] = i
					index_length[j] += 1
			else:
				x = w
				NCRsum[i] = [0 for j in range(w)]
				precomputetill[i] = [1 for j in range(w)]
				NCRsum[i][0] = x
				precomputetill[i][0] = x + 1
				precompute[0][index_length[0]] = i
				index_length[0] += 1
				for j in range(1, w // 2):
					x = x * (w - j) // (j + 1)
					NCRsum[i][j] = x % mod
					precompute[j][index_length[j]] = i
					index_length[j] += 1
				for j in range(w // 2, w - 1):
					NCRsum[i][j] = NCRsum[i][w - j - 2]
					precompute[j][index_length[j]] = i
					index_length[j] += 1
				NCRsum[i][-1] = 1
				if w > 1:
					precompute[w - 1][index_length[w - 1]] = i
					index_length[w - 1] += 1
				for j in range(1, w):
					precomputetill[i][j] = (precomputetill[i][j - 1] + NCRsum[i][j]) % mod
				ifdone[w] = True
				ifdonepos[w] = i
		finalans = [0 for i in range(N + 1)]
		prefprod = [[] for i in range(len(precompute))]
		suffixprod = [[] for i in range(len(precompute))]
		for i in range(maxg):
			if i != 0:
				ki = precompute[i]
				prefprod[i] = [1 for i in range(len(ki))]
				suffixprod[i] = [1 for i in range(len(ki))]
				for j in range(1, len(ki)):
					prefprod[i][j] = prefprod[i][j - 1] * precomputetill[ki[j - 1]][i - 1] % mod
					prefprod[i][j] %= mod
				suffixprod[i][len(ki) - 1] = 1
				for j in range(len(ki) - 2, -1, -1):
					suffixprod[i][j] = suffixprod[i][j + 1] * precomputetill[ki[j + 1]][i] % mod
					suffixprod[i][j] %= mod
		producttill = 1
		curr = 1
		stable = [[] for i in range(N + 1)]
		for i in y:
			stable[i] = [0 for j in range(dic[i])]
		ans = 1
		for i in range(maxg):
			ki = precompute[i]
			curr = producttill
			pi = prefprod[i]
			si = suffixprod[i]
			for j in range(len(ki) - 1, -1, -1):
				if i == 0:
					if j == len(ki) - 1:
						stable[ki[j]][i] = 1
					else:
						ans *= precomputetill[ki[j + 1]][i] % mod
						ans %= mod
						stable[ki[j]][i] = ans
					if dic[ki[j]] == i + 1:
						producttill *= precomputetill[ki[j]][i]
				else:
					ans = pi[j] * si[j] % mod * curr % mod
					stable[ki[j]][i] = ans
					if dic[ki[j]] == i + 1:
						producttill = producttill * precomputetill[ki[j]][i] % mod
						producttill %= mod
		for i in range(1, N + 1):
			for j in range(len(stable[i])):
				finalans[i] += stable[i][j] * NCRsum[i][j] % mod
				finalans[i] %= mod
		for i in range(1, N + 1):
			print(finalans[i], end=' ')
		print()


M = 1000000007
N = 500005
fact = [0 for i in range(N)]
fact[0] = 1
for i in range(1, N):
	fact[i] = fact[i - 1] * i % M
inv_fact = [0 for i in range(N)]
inv_fact[N - 1] = pow(fact[N - 1], M - 2, M)
for i in range(N - 2, -1, -1):
	inv_fact[i] = (i + 1) * inv_fact[i + 1] % M

def ncr(n1, r1):
	return fact[n1] * inv_fact[r1] % M * inv_fact[n1 - r1] % M

def inv(v):
	return pow(v, M - 2, M)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = [0 for i in range(n + 1)]
	for x in a:
		cnt[x] += 1
	st = sorted(list(set(a)))
	mul_arr_small = [1 for i in range(n + 5)]
	prefix_small = [1 for i in range(n + 5)]
	mul_arr_small[0] = 0
	final_add = []
	for x in st:
		l = [0 for i in range(cnt[x])]
		for i in range(cnt[x]):
			l[i] = ncr(cnt[x], i + 1)
		final_add.append(l)
	for index in range(len(st)):
		x = st[index]
		temp = 1
		for i in range(cnt[x]):
			temp = temp * prefix_small[i + 1] % M
			final_add[index][i] = final_add[index][i] * (temp * mul_arr_small[i + 1]) % M % M
		temp = 0
		for i in range(cnt[x]):
			temp = (temp + ncr(cnt[x], i)) % M
			mul_arr_small[i + 1] = mul_arr_small[i + 1] * temp % M
		temp = (temp + 1) % M
		prefix_small[cnt[x] + 1] = prefix_small[cnt[x] + 1] * temp % M
	mul_arr_big = [1 for i in range(n + 5)]
	prefix_big = [1 for i in range(n + 5)]
	for index in range(len(st) - 1, -1, -1):
		x = st[index]
		temp = 1
		for i in range(cnt[x]):
			temp = temp * prefix_big[i + 1] % M
			final_add[index][i] = final_add[index][i] * (temp * mul_arr_big[i + 1]) % M % M
		temp = 1
		for i in range(cnt[x]):
			temp = (temp + ncr(cnt[x], i + 1)) % M
			mul_arr_big[i + 1] = mul_arr_big[i + 1] * temp % M
		prefix_big[cnt[x] + 1] = prefix_big[cnt[x] + 1] * temp % M
	ans = {}
	for index in range(len(st)):
		a = 0
		for i in range(cnt[st[index]]):
			a = (a + final_add[index][i]) % M
		ans[st[index]] = a
	for i in range(1, n + 1):
		if i in ans:
			print(ans[i], end=' ')
		else:
			print(0, end=' ')
	print()


import math
from collections import OrderedDict

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	if inv == -1:
		return inv
	else:
		return inv * a % m
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	count = []
	z = 10 ** 9 + 7
	for j in range(n):
		count.append([0, j + 1])
	for j in range(n):
		count[arr[j] - 1][0] += 1
	num = 0
	for j in range(n):
		if count[j][0] == 1:
			num += 1
	if num == n:
		x = 10 ** 9 + 7
		lis = [0] * n
		lis[-1] = 1
		for j in range(2, n + 1):
			lis[-j] = lis[-j + 1] * 2 % x
		print(' '.join((str(x) for x in lis)))
	else:
		realCount = []
		for j in range(n):
			if count[j][0] != 0:
				realCount.append(count[j])
		len1 = len(realCount)
		matrix = []
		for j in range(len1):
			lis = [1]
			s = 1
			for k in range(realCount[j][0]):
				x = realCount[j][0] - k
				y = k + 1
				temp = modDivide(s * x, y, z)
				if temp == -1:
					s = s * x // y
				else:
					s = temp
				lis.append(s % z)
			matrix.append(lis)
		box = []
		for j in range(len1):
			lis = [1]
			for k in range(1, realCount[j][0] + 1):
				s = lis[-1] + matrix[j][k]
				s %= z
				lis.append(s)
			box.append(lis)
		impBox = []
		for j in range(1, len1 + 1):
			lis = []
			for l in range(realCount[-j][0] + 1):
				lis.append(box[-j][l])
			impBox.append(lis)
		dict1 = OrderedDict()
		for j in range(len1):
			dict1[j] = box[j]
		freq = 0
		while dict1:
			s = 1
			for key in list(dict1.keys()):
				if freq == matrix[key][1]:
					del dict1[key]
				else:
					s = s * dict1[key][freq]
					s %= z
					box[key][freq] = s
			freq += 1
		dict2 = OrderedDict()
		for j in range(len1):
			dict2[j] = impBox[j]
		freq = 0
		while dict2:
			s = 1
			for key in list(dict2.keys()):
				s = s * dict2[key][freq]
				s %= z
				impBox[key][freq] = s
				if freq == matrix[len1 - 1 - key][1]:
					del dict2[key]
			freq += 1
		impMatrix = []
		for j in range(len1):
			lis = [1]
			for k in range(1, realCount[j][0] + 1):
				s = lis[-1] + matrix[j][k]
				s %= z
				lis.append(s)
			impMatrix.append(lis)
		dict3 = OrderedDict()
		for j in range(len1):
			dict3[j] = impMatrix[j]
		lis = [1]
		ans = [0] * n
		freq = 1
		while dict3:
			s = 0
			p = 0
			len2 = len(dict3)
			prev = -1
			array = OrderedDict()
			for key in list(dict3.keys()):
				if p != 0:
					array[prev] = key
				p += 1
				prev = key
			prev = -1
			num1 = []
			for key in list(dict3.keys()):
				temp = matrix[key][freq]
				if len2 == 1:
					temp = temp * lis[-1] % z
				elif s == 0:
					temp = temp * impBox[len1 - 1 - array[key]][freq] % z
					temp = temp * lis[-1] % z
				elif s == len2 - 1:
					temp = temp * box[prev][freq - 1] % z
					temp = temp * lis[-1] % z
				else:
					temp = temp * box[prev][freq - 1] % z
					temp = temp * impBox[len1 - 1 - array[key]][freq] % z
					temp = temp * lis[-1] % z
				prev = key
				s += 1
				p += 1
				ans[realCount[key][1] - 1] = (ans[realCount[key][1] - 1] + temp) % z
				if freq == matrix[key][1]:
					num1.append(dict3[key][-1])
					del dict3[key]
					p -= 1
			len3 = len(num1)
			num = 1
			for j in range(len3):
				num = num * num1[j] % z
			lis.append(lis[-1] * num % z)
			freq += 1
		print(' '.join((str(x) for x in ans)))


import sys
import math
from collections import defaultdict, Counter, deque
input = sys.stdin.readline

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m
m = 10 ** 9 + 7
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	v = {}
	ma = 1
	for j in range(1, n + 1):
		v[a[j - 1]] = v.get(a[j - 1], 0) + 1
		ma = max(ma, v[a[j - 1]])
	if ma == 1:
		for j in range(1, n + 1):
			print(pow(2, n - j, m), end=' ')
		print()
		continue
	v = sorted(v.items())
	v1 = len(v)
	pre = {}
	suf = {}
	for j in range(v1):
		suf[v[j][1]] = suf.get(v[j][1], 0) + 1
	fact = [1]
	inverse = [1]
	for j in range(1, ma + 1):
		fact.append(fact[j - 1] * j % m)
		inverse.append(power(fact[j], m - 2, m))
	mul = defaultdict(list)
	for j in suf:
		mul[j].append(inverse[j])
		for k in range(1, j + 1):
			mul[j].append(mul[j][k - 1])
			mul[j][k] = (mul[j][k] + inverse[k] * inverse[j - k] % m) % m
	if n * len(suf) < ma * v1:
		ans = [0] * (n + 1)
		for j in range(v1):
			suf[v[j][1]] -= 1
			p = 1
			while p <= v[j][1]:
				curr = fact[v[j][1]] * (inverse[p] * inverse[v[j][1] - p]) % m % m
				for k in suf:
					curr = curr * pow(fact[k] * mul[k][min(p, k)] % m, suf[k], m) % m
				for k in pre:
					curr = curr * pow(fact[k] * mul[k][min(p - 1, k)] % m, pre[k], m) % m
				ans[v[j][0]] = (ans[v[j][0]] + curr) % m
				p += 1
			pre[v[j][1]] = pre.get(v[j][1], 0) + 1
		print(*ans[1:])
		continue
	final = defaultdict(list)
	final2 = defaultdict(deque)
	for j in range(ma + 1):
		final[j].append(mul[v[0][1]][min(j, v[0][1])])
		for k in range(1, v1):
			final[j].append(final[j][k - 1])
			final[j][k] = final[j][k] * mul[v[k][1]][min(j, v[k][1])] % m
		final[j].append(1)
		final2[j].append(1)
		final2[j].appendleft(mul[v[-1][1]][min(j, v[-1][1])])
		for k in range(v1 - 2, -1, -1):
			final2[j].appendleft(final2[j][0])
			final2[j][0] = final2[j][0] * mul[v[k][1]][min(j, v[k][1])] % m
	ans = [0] * (n + 1)
	all = 1
	for j in range(v1):
		all = all * fact[v[j][1]] % m
		p = 1
		while p <= v[j][1]:
			curr = inverse[p] * inverse[v[j][1] - p] % m
			curr = curr * final2[p][j + 1] % m * final[p - 1][j - 1] % m
			ans[v[j][0]] = (ans[v[j][0]] + curr) % m
			p += 1
	for j in range(1, n + 1):
		print(all * ans[j] % m, end=' ')
	print()


from collections import Counter
mod = 10 ** 9 + 7
(hash1, hashn) = ({}, {})

def power(x, y):
	res = 1
	x = x % mod
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % mod
		y = y >> 1
		x = x * x % mod
	return res

def nCr(n, r):
	r = min(r, n - r)
	num = reduce(op.mul, range(n, n - r, -1), 1)
	den = reduce(op.mul, range(1, r + 1), 1)
	return num // den % mod

def helper2(curr, t):
	result = 1
	while t:
		if t & 1:
			result = result * curr % mod
		curr = curr * curr % mod
		t = t >> 1
	return result % mod

def helper(curr):
	return helper2(curr, mod - 2)

def NCR(n, r):
	if r == 0:
		return 1
	else:
		if factorial[n - r] in hash1:
			temp = hash1[factorial[n - r]]
		else:
			temp = helper(factorial[n - r])
			hash1[factorial[n - r]] = temp
		if factorial[r] in hash1:
			temp2 = hash1[factorial[r]]
		else:
			temp2 = helper(factorial[r])
			hash1[factorial[r]] = temp2
		return factorial[n] * temp % mod * temp2 % mod
t = int(input())
factorial = [1, 1]
for i in range(2, 500001):
	factorial.append(i * factorial[-1] % mod)

def func(A, n):
	if len(set(A)) == 1:
		final = [0] * n
		k = A[0]
		final[k - 1] = power(2, n) - 1
		return final
	mapper = Counter(A)
	final = [0] * n
	A.sort()
	(C, R) = ([1] * (n + 1), [1] * (n + 1))
	C.extend([0, 0])
	for i in mapper:
		curr = 1
		for j in range(1, mapper[i] + 1):
			if (mapper[i], j) in hashn:
				temp = hashn[mapper[i], j]
			else:
				temp = NCR(mapper[i], j)
				hashn[mapper[i], j] = temp
			curr = (curr + temp) % mod
			C[j] = C[j] * curr % mod
		R[mapper[i] + 1] = R[mapper[i] + 1] * curr % mod
	curr2 = 1
	for i in range(1, n + 1):
		curr2 = curr2 * R[i] % mod
		C[i] = C[i] * curr2 % mod
	for i in range(1, n + 1):
		answer = 0
		curr = 1
		for j in range(1, mapper[i] + 1):
			if (mapper[i], j) in hashn:
				curr3 = hashn[mapper[i], j]
			else:
				curr3 = NCR(mapper[i], j)
				hashn[mapper[i], j] = curr3
			curr = (curr + curr3) % mod
			C[j] = C[j] * helper(curr) % mod
			curr2 = curr3
			curr3 = curr3 * C[j] % mod
			C[j] = C[j] * (curr - curr2 + mod) % mod % mod
			answer = (answer + curr3) % mod
		final[i - 1] = answer % mod
	return final
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	final = func(A, n)
	for l in final:
		print(l, end=' ')
	print()


from math import ceil, sqrt
MOD = int(1000000000.0 + 7)

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

def add(a, b):
	return (a + b) % MOD

class Combination:
	kfact = []
	invkfact = []
	memo = {}
	c_memo = {}

	def __init__(self, max_n):
		self.kfact = [0 for i in range(max_n + 1)]
		self.invkfact = [0 for i in range(max_n + 1)]
		self.buildkfact(max_n)
		self.buildinvkfact(max_n)

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

	def buildkfact(self, max_n):
		self.kfact[0] = 1
		for i in range(1, max_n + 1):
			self.kfact[i] = mult(self.kfact[i - 1], i)

	def buildinvkfact(self, max_n):
		self.invkfact[max_n] = self.mod_inv(self.kfact[max_n])
		for i in range(max_n - 1, 0, -1):
			self.invkfact[i] = mult(self.invkfact[i + 1], i + 1)
		self.invkfact[0] = 1

	def C(self, n, r):
		return mult(self.kfact[n], mult(self.invkfact[n - r], self.invkfact[r]))

	def set_freq(self, freq):
		self.prebuild(freq)

	def prebuild(self, freq):
		for elem in freq:
			S = []
			n = freq[elem]
			for i in range(n + 1):
				S.append(self.C(n, i))
			p = pow(2, n, MOD)
			for i in range(1, n + 1):
				S[i] = add(S[i], S[i - 1])
			for i in range(n + 1):
				S[i] = mult(S[i], self.mod_inv(p))
			self.memo[n] = S

def freq(a):
	m = {}
	for e in a:
		if e in m:
			m[e] += 1
		else:
			m[e] = 1
	return m
comb = Combination(500001)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	freq_arr = freq(a)
	comb.set_freq(freq_arr)
	ans = [0 for i in range(n + 1)]
	res_back_memo = [1 for i in range(n + 1)]
	res_front_memo = [1 for i in range(n + 1)]
	backward = {}
	forward = {}
	back_mult = [1 for i in range(n + 1)]
	for i in range(1, n + 1):
		if i in freq_arr:
			back_mult[i] = mult(back_mult[i - 1], pow(2, freq_arr[i], MOD))
		else:
			back_mult[i] = back_mult[i - 1]
	front_mult = [1 for i in range(n + 2)]
	for i in range(n, 0, -1):
		if i in freq_arr:
			front_mult[i] = mult(front_mult[i + 1], pow(2, freq_arr[i], MOD))
		else:
			front_mult[i] = front_mult[i + 1]
	for e in range(1, n + 1):
		if e in freq_arr:
			freq_e = freq_arr[e]
			for i in range(1, freq_e + 1):
				res = mult(res_back_memo[i], back_mult[e - 1])
				backward[e, i] = res
			for i in range(1, freq_e + 1):
				res_back_memo[i] = mult(res_back_memo[i], comb.memo[freq_arr[e]][i - 1])
	for e in range(n, 0, -1):
		if e in freq_arr:
			freq_e = freq_arr[e]
			for i in range(1, freq_e + 1):
				res = mult(res_front_memo[i], front_mult[e + 1])
				forward[e, i] = res
			for i in range(1, freq_e + 1):
				res_front_memo[i] = mult(res_front_memo[i], comb.memo[freq_arr[e]][i])
	for e in range(1, n + 1):
		if e in freq_arr:
			for i in range(1, freq_arr[e] + 1):
				ans[e] = add(ans[e], mult(comb.C(freq_arr[e], i), mult(forward[e, i], backward[e, i])))
	for i in range(1, n + 1):
		print(ans[i], end=' ')
	print()


N = 500001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)
naturalNumInverse[0] = naturalNumInverse[1] = 1
for i in range(2, N + 1, 1):
	naturalNumInverse[i] = naturalNumInverse[1000000007 % i] * (1000000007 - 1000000007 // i) % 1000000007
factorialNumInverse[0] = factorialNumInverse[1] = 1
for i in range(2, N + 1, 1):
	factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % 1000000007
fact[0] = 1
for i in range(1, N + 1):
	fact[i] = fact[i - 1] * i % 1000000007

def Binomial(N, R):
	return fact[N] * factorialNumInverse[R] % 1000000007 * factorialNumInverse[N - R] % 1000000007

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cts = {}
	rc = {}
	ans = [0 for _ in range(n)]
	acts = [0 for _ in range(n)]
	for x in a:
		acts[x - 1] += 1
	myarray = []
	for x in range(n, 0, -1):
		if acts[x - 1] > 0:
			cts[x] = acts[x - 1]
			myarray.append(x)
			rc[x] = 1
	nl = []
	nextlist = []
	for y in range(1, max(acts) + 1):
		justlist = []
		nextlist = []
		for x in myarray:
			justlist.append(x)
			if acts[x - 1] > y:
				nextlist.append(x)
		nl.append(justlist)
		myarray = nextlist
	p = 1
	for (g, x) in enumerate(nl):
		for i in x:
			c = Binomial(cts[i], g + 1)
			p = p * modInverse(rc[i], 1000000007) % 1000000007
			ans[i - 1] = (ans[i - 1] + p * c % 1000000007) % 1000000007
			rc[i] = (rc[i] + c) % 1000000007
			p = rc[i] * p % 1000000007
	for i in ans:
		print(i, end=' ')
	print()


comb_sum = [[1].copy() for _ in range(500001)]
combination_hash = {}
com_num = [[].copy() for _ in range(500001)]
com_den = [[].copy() for _ in range(500001)]
MOD_VAL = 1000000007

def combinations(n, r):
	r = min(n - r, r)
	if r == 0:
		return 1
	if combination_hash.get((n, r)) is not None:
		return combination_hash[n, r]
	p = 1000000007
	num = den = 1
	if len(com_num[n]) != 0:
		num = com_num[n][-1]
		den = com_den[n][-1]
	for i in range(len(com_num[n]), r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
		com_num[n].append(num)
		com_den[n].append(den)
	answer = num * pow(den, p - 2, p) % p
	combination_hash[n, r] = answer
	return answer

def pre_compute_comb_sum(freqs):
	for freq in freqs:
		cache = comb_sum[freq]
		if len(cache) > freq:
			continue
		local_possible = 1
		for i in range(1, freq + 1):
			local_possible += combinations(freq, i)
			local_possible %= MOD_VAL
			cache.append(local_possible)

def pre_compute_sum_for(count_dict, n):
	global pre_mul_for
	prefix_mul = [[]]
	c_psum = [0]
	for i in range(1, n + 1):
		if i not in count_dict:
			c_psum.append(c_psum[-1])
			continue
		c_psum.append(c_psum[-1] + count_dict[i])
	recents = [-1] * 500001
	for key in range(1, n + 1):
		if key not in count_dict:
			prefix_mul.append(prefix_mul[-1])
			continue
		prefix = []
		for i in range(1, count_dict[key] + 1):
			cur_comb_sum = comb_sum[count_dict[key]][i]
			if recents[i] == -1:
				prev_prefix_mul = pow(2, c_psum[key - 1], MOD_VAL)
				prefix.append((prev_prefix_mul % MOD_VAL, prev_prefix_mul * cur_comb_sum % MOD_VAL))
			else:
				pow_2 = c_psum[key - 1] - c_psum[recents[i]]
				pow_2 = pow(2, pow_2, MOD_VAL)
				recent_prefix_sum = prefix_mul[recents[i]][i - 1][1]
				prefix.append((pow_2 * recent_prefix_sum % MOD_VAL, pow_2 * recent_prefix_sum * cur_comb_sum % MOD_VAL))
			recents[i] = key
		prefix_mul.append(prefix)
	pre_mul_for = prefix_mul

def pre_compute_sum_rev(count_dict, n):
	global pre_mul_rev
	prefix_mul = [[]]
	c_psum = [0]
	for i in range(n, 0, -1):
		if i not in count_dict:
			c_psum.append(c_psum[-1])
			continue
		c_psum.append(c_psum[-1] + count_dict[i])
	c_psum.append(0)
	c_psum.reverse()
	recents = [-1] * 500001
	for key in range(n, 0, -1):
		if key not in count_dict:
			prefix_mul.append(prefix_mul[-1])
			continue
		prefix = []
		for i in range(1, count_dict[key] + 1):
			cur_comb_sum = comb_sum[count_dict[key]][i]
			if recents[i] == -1:
				prev_prefix_mul = pow(2, c_psum[key + 1], MOD_VAL)
				prefix.append((prev_prefix_mul % MOD_VAL, prev_prefix_mul * cur_comb_sum % MOD_VAL))
			else:
				pow_2 = c_psum[key + 1] - c_psum[recents[i]]
				pow_2 = pow(2, pow_2, MOD_VAL)
				recent_prefix_sum = prefix_mul[n - recents[i] + 1][i - 1][1]
				prefix.append((pow_2 * recent_prefix_sum % MOD_VAL, pow_2 * recent_prefix_sum * cur_comb_sum % MOD_VAL))
			recents[i] = key
		prefix_mul.append(prefix)
	prefix_mul.append([])
	prefix_mul.reverse()
	del prefix_mul[-1]
	pre_mul_rev = prefix_mul

def get_subsequence_count(num, count):
	if count == 1:
		return pre_mul_rev[num][count - 1][0]
	else:
		return pre_mul_for[num][count - 2][0] * pre_mul_rev[num][count - 1][0] % MOD_VAL

def solution(n, nums):
	global prefix_sums_for, prefix_sums_rev
	count_dict = {}
	for num in nums:
		count_dict[num] = count_dict.get(num, 0) + 1
	nums_present = list(count_dict.keys())
	nums_present.sort()
	pre_compute_comb_sum(set(count_dict.values()))
	pre_compute_sum_for(count_dict, n)
	pre_compute_sum_rev(count_dict, n)
	answers = []
	for num in range(1, n + 1):
		if num not in count_dict:
			answers.append('0')
			continue
		answer = 0
		for int_count in range(1, count_dict[num] + 1):
			answer += combinations(count_dict[num], int_count) % 1000000007 * (get_subsequence_count(num, int_count) % 1000000007)
		answers.append(str(answer % 1000000007))
	return ' '.join(answers)
T = int(input())
while T != 0:
	n = int(input())
	nums = [int(a) for a in input().split(' ')]
	print(solution(n, nums))
	T -= 1


mod = 10 ** 9 + 7
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	dic = {}
	mxn = 0
	for i in range(N):
		if A[i] in dic:
			dic[A[i]] += 1
		else:
			dic[A[i]] = 1
		mxn = max(mxn, dic[A[i]])
	if len(dic.keys()) == 1:
		x = pow(2, N, mod) - 1
		j = A[0]
		for i in range(N):
			if i == A[0] - 1:
				print(x, end=' ')
			else:
				print(0, end=' ')
	else:
		kaunlen = [0 for i in range(mxn)]
		for i in dic.keys():
			for j in range(dic[i]):
				kaunlen[j] += 1
		kaunlenindex = [0 for i in range(mxn)]
		kaun = [[0 for j in range(kaunlen[i])] for i in range(mxn)]
		y = [0 for i in range(len(dic.keys()))]
		io = 0
		for i in range(1, N + 1):
			if i in dic:
				y[io] = i
				io += 1
		K = [[] for i in range(N + 1)]
		sumtill = [[] for i in range(N + 1)]
		ifdone = [False for i in range(N + 1)]
		ifdonepos = [0 for i in range(N + 1)]
		for i in y:
			w = dic[i]
			if ifdone[w]:
				K[i] = K[ifdonepos[w]].copy()
				sumtill[i] = sumtill[ifdonepos[w]].copy()
				for j in range(w):
					kaun[j][kaunlenindex[j]] = i
					kaunlenindex[j] += 1
			else:
				x = w
				K[i] = [0 for j in range(w)]
				sumtill[i] = [1 for j in range(w)]
				K[i][0] = x
				sumtill[i][0] = x + 1
				kaun[0][kaunlenindex[0]] = i
				kaunlenindex[0] += 1
				for j in range(1, w // 2):
					x = x * (w - j) // (j + 1)
					K[i][j] = x % mod
					kaun[j][kaunlenindex[j]] = i
					kaunlenindex[j] += 1
				for j in range(w // 2, w - 1):
					K[i][j] = K[i][w - j - 2]
					kaun[j][kaunlenindex[j]] = i
					kaunlenindex[j] += 1
				K[i][-1] = 1
				if w > 1:
					kaun[w - 1][kaunlenindex[w - 1]] = i
					kaunlenindex[w - 1] += 1
				for j in range(1, w):
					sumtill[i][j] = (sumtill[i][j - 1] + K[i][j]) % mod
				ifdone[w] = True
				ifdonepos[w] = i
		finans = [0 for i in range(N + 1)]
		preprod = [[] for i in range(len(kaun))]
		sufprod = [[] for i in range(len(kaun))]
		for i in range(mxn):
			if i != 0:
				ki = kaun[i]
				preprod[i] = [1 for i in range(len(ki))]
				sufprod[i] = [1 for i in range(len(ki))]
				for j in range(1, len(ki)):
					preprod[i][j] = preprod[i][j - 1] * sumtill[ki[j - 1]][i - 1] % mod
					preprod[i][j] %= mod
				sufprod[i][len(ki) - 1] = 1
				for j in range(len(ki) - 2, -1, -1):
					sufprod[i][j] = sufprod[i][j + 1] * sumtill[ki[j + 1]][i] % mod
					sufprod[i][j] %= mod
		prodtill = 1
		curr = 1
		finanstable = [[] for i in range(N + 1)]
		for i in y:
			finanstable[i] = [0 for j in range(dic[i])]
		ans = 1
		for i in range(mxn):
			ki = kaun[i]
			curr = prodtill
			pi = preprod[i]
			si = sufprod[i]
			for j in range(len(ki) - 1, -1, -1):
				if i == 0:
					if j == len(ki) - 1:
						finanstable[ki[j]][i] = 1
					else:
						ans *= sumtill[ki[j + 1]][i] % mod
						ans %= mod
						finanstable[ki[j]][i] = ans
					if dic[ki[j]] == i + 1:
						prodtill *= sumtill[ki[j]][i]
				else:
					ans = pi[j] * si[j] % mod * curr % mod
					finanstable[ki[j]][i] = ans
					if dic[ki[j]] == i + 1:
						prodtill = prodtill * sumtill[ki[j]][i] % mod
						prodtill %= mod
		for i in range(1, N + 1):
			for j in range(len(finanstable[i])):
				finans[i] += finanstable[i][j] * K[i][j] % mod
				finans[i] %= mod
		for i in range(1, N + 1):
			print(finans[i], end=' ')
		print()