B. Subset Counting
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Given three integers $$$n,k$$$ and $$$m$$$. Let $$$S=\{i\mid 1\le i\le nm+k,i\in \mathbb Z\}$$$. For all integers $$$r$$$ where $$$0\le r \lt m$$$, you need to output the number of sets $$$T$$$ such that

  • $$$T$$$ is a subset of $$$S$$$.
  • The sum of elements in $$$T$$$ is modulo $$$m$$$ exactly $$$r$$$.
Input

The only line of the input contains three integers $$$n\ (0\le n\le 10^{13})$$$, $$$k\ (0\le k \lt \min(m,500),nm+k \gt 0)$$$ and $$$m\ (1\le m\le 10^5)$$$ as described above.

Output

Output $$$m$$$ integers in a line, the $$$i$$$-th of which indicates the number of subsets modulo $$$998\,244\,353$$$ when $$$r=i-1$$$.

Examples
Input
1 1 2
Output
4 4
Input
1919 8 10
Output
577613260 577613260 822345879 577613260 822345879 577613260 577613260 822345879 577613260 822345879