This is a template problem.

Given positive integers $n, q, mod$. It is guaranteed that $mod$ is a prime number.

For a rooted tree $T$ with root $1$, let $s(T)$ be the maximum number of non-isomorphic subtrees that can be selected from this tree (i.e., the number of essentially different subtrees in this tree). The weight of this tree is $w(T) = q^{s(T)}$.

For all $1 \le m \le n$, output the sum of weights of all labeled rooted trees with $m$ nodes and root $1$, modulo $mod$.

Two rooted trees $T_1$ and $T_2$ are isomorphic if and only if they have the same size, and there exists a vertex permutation $\sigma$ such that in $T_1$, $i$ is an ancestor of $j$ if and only if in $T_2$, $\sigma(i)$ is an ancestor of $\sigma(j)$.

Input

Two integers $n, q, mod$ on a single line.

Output

Output $n$ lines, where the $m$-th line represents the answer for $m$ nodes.

Examples

Input 1

3 2 998244353

Output 1

2
4
20

Note 1

When $n=3, q=2, mod=998244353$, there are three different labeled rooted trees with three nodes and root $1$. Two of them satisfy $w(T)=2^3$, and the other satisfies $w(T)=2^2$. Therefore, the answer is $(2 \times 2^3+2^2) \bmod 998244353 = 20$.

Input 2

11 4514 998244353

Output 2

4514
20376196
299712732
706663250
721357660
977589073
794002114
369586566
663682963
347458730
524354925

Input 3

40 787788 998244853

Output 3

787788
699879231
445785131
857102003
759492151
898159394
575712517
634469464
412999753
814233648
333451903
852329440
584109489
270769240
532457985
79235443
2228568
266810999
310877128
614605839
485785485
338520973
113751992
692026056
664258393
650448721
505881810
237159658
107178163
629910112
513627947
915509519
737809847
921731327
233492829
202989716
728903945
776060784
105388817
121481849

Constraints

For all test cases, it is guaranteed that $n = 100, 10^8 \le mod \le 1.01 \times 10^9, 1 \le q < mod$, and $mod$ is a prime number.

This problem consists of $1$ subtask, worth $100$ points. Your score for this subtask is the minimum score among all test points in the subtask.

You must output $n$ numbers according to the output format, but you may output incorrect answers. If you output $c$ correct answers, your score is calculated as follows:

• For $0 \le c \le 20$, your score is $2c$ points.
• For $21 \le c \le 60$, your score is $c + 20$ points.
• For $61 \le c \le 100$, your score is $\lfloor \frac{c}{2}\rfloor + 50$ points.

You can use the following code to speed up your modulo operations.

struct fastmod {
  typedef unsigned long long u64;
  typedef __uint128_t u128;

  int m;
  u64 b;

  fastmod(int m) : m(m), b(((u128)1 << 64) / m) {}
  int reduce(u64 a) {
    u64 q = ((u128)a * b) >> 64;
    int r = a - q * m;
    return r < m ? r : r - m;
  }
} z(2);
void solve() {
    long long mod = 998244353, qwq = 1e9;
    z = fastmod(mod);
    cout << z.reduce(qwq) << ' ' << qwq % mod << '\n';
}