Isomorphic Subtree Counting in Rooted Trees

Given three positive integers \(n\), \(q\), and \(mod\) (where \(mod\) is prime), consider all labeled rooted trees with vertices \(\{1,2,\dots,m\}\) having root \(1\) for every \(1 \le m \le n\). For a rooted tree \(T\), let its subtree rooted at vertex \(v\) be the tree induced by \(v\) and all of its descendants, with the structure inherited from \(T\). Define \(s(T)\) to be the maximum number of subtrees among \(\{T_v : v \in T\}\) which are pairwise non-isomorphic (i.e. no two subtrees have the same structure up to renaming of vertices).

The weight of \(T\) is defined as \(w(T)=q^{s(T)}\). Your task is to compute, for every \(1\le m\le n\), the sum of \(w(T)\) over all rooted trees \(T\) on \(m\) vertices with root \(1\), taken modulo \(mod\).

Two rooted trees \(T_1\) and \(T_2\) (of the same size) are said to be isomorphic if there exists a permutation \(\sigma\) on their vertices such that for any two vertices \(i\) and \(j\), \(i\) is an ancestor of \(j\) in \(T_1\) if and only if \(\sigma(i)\) is an ancestor of \(\sigma(j)\) in \(T_2\).

inputFormat

The input consists of a single line containing three integers \(n\), \(q\), and \(mod\) separated by spaces.

\(1 \le n \le \text{small}\) (the test cases will be chosen so that a brute-force approach is feasible), \(q \ge 1\), and \(mod\) is a prime number.

outputFormat

Output \(n\) integers separated by spaces. The \(m\)-th integer should be the sum of the weights \(w(T)=q^{s(T)}\) for all labeled rooted trees with \(m\) vertices (and root 1), taken modulo \(mod\).

sample

1 2 1000003

2