Derangements and Cycle Polynomial Sum

Consider a permutation (\pi) of length (m) (with (1 \le m \le n)) that has no fixed points (i.e. there is no index (i) such that (\pi_i = i)). When viewing (\pi) as a permutation written in disjoint cycle form, let (\text{cyc}{\pi}) denote the number of cycles in the cycle decomposition. You are also given a polynomial (F(x)) of degree (k-1) given by [ F(x)=a_0+a_1x+\cdots+a{k-1}x^{k-1}, ] where the coefficients (a_0, a_1, \dots, a_{k-1}) are provided as input.

For each integer (m) from 1 to (n), compute [ S(m)=\sum_{\pi} F\Big(\text{cyc}_{\pi}\Big), ] where the summation is taken over all derangements (permutations with no fixed points) (\pi) of ({1,2,\dots,m}).

It is known that a derangement exists only if (m \ge 2) (with the convention that the unique permutation of 0 elements exists, but we do not consider (m=0)), and for (m=1) the answer is defined to be 0.

The answer for each (m) should be printed on a separate line in the order (m=1,2,\dots,n).

inputFormat

The first line of input contains two integers (n) and (k) (where (1 \le n \le N) for some small (N) and (k \ge 1)). The second line contains (k) space-separated integers: (a_0, a_1, \dots, a_{k-1}), which are the coefficients of the polynomial (F(x)=a_0+a_1x+\cdots+a_{k-1}x^{k-1}).

outputFormat

Output (n) lines. The (m)-th line (for (1 \le m \le n)) should contain a single integer, which is the value of (S(m)=\sum_{\pi}F(\text{cyc}_{\pi})) over all derangements (\pi) of length (m). For (m=1), output 0.

sample

2 2
1 1

0
2