H. 子序列、达标率与期望
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
在本次期末考试中,有大约一半的同学没有达到平均分,希望他们能再接再厉。
— 某教师语录

对于一个长度为 $$$m$$$ 的整数序列 $$$c = [c_1, c_2, \cdots, c_m]$$$,

我们定义它的均值 $$$f(c)$$$ 为序列元素的算术平均值。即:

$$$$$$ f ( c ) = \frac{1}{m} \sum_{i = 1}^{m} c_i $$$$$$

我们定义它的达标率 $$$g(c)$$$ 为序列中大于均值的元素所占比例。即:

$$$$$$ g( c ) = \frac{1}{m} \sum_{\substack{1 \leq i \leq m \\ c_i \gt f ( c )}} 1 $$$$$$

给定一个长度为 $$$n$$$ 的正整数序列 $$$[a_1, a_2, a_3, \cdots, a_n]$$$。请你对于 $$$k = 2, 3, 4, \cdots, n$$$ 依次计算:

如果从它全部的 $$$C (n, k)$$$ 个长度为 $$$k$$$ 的子序列中等概率随机选取一个子序列,求其达标率的期望值。

由于答案可能为分数,请输出其对 $$$998 \, 244 \, 353$$$ 取模的结果。

具体而言,可以证明,答案可以被表示为最简分数 $$$\frac{p}{q}$$$($$$p$$$ 与 $$$q$$$ 互质且 $$$q$$$ 不被 $$$998 \, 244 \, 353$$$ 整除)。你需要输出满足 $$$0 \leq x \lt 998 \, 244 \, 353$$$ 且 $$$x \cdot q \equiv p \pmod{998 \, 244 \, 353}$$$ 的整数 $$$x$$$。

Input

第一行一个整数 $$$n$$$($$$2 \leq n \leq 50$$$),表示序列长度。

第二行 $$$n$$$ 个整数 $$$a_1, a_2, a_3, \cdots, a_n$$$($$$0 \leq a_i \leq n$$$)表示序列中的元素。

Output

输出 $$$n - 1$$$ 个整数,依次表示 $$$k = 2, 3, 4, \cdots, n$$$ 时的答案对 $$$998 \, 244 \, 353$$$ 取模后的结果。

Examples
Input
6
1 1 4 5 1 4
Output
765320671 66549624 499122177 499122177 499122177
Input
9
9 9 8 2 4 4 3 5 3
Output
207967574 122799901 485257672 179050178 297096534 194103069 623902721 332748118