Construct a tree using the following classic method: for $i = 2 \sim n$, randomly choose a node from $1 \sim i-1$ to be the parent of $i$.
Let $f_u$ be the size of the subtree rooted at node $u$ raised to the power of $k$. For each node $u$, calculate the expected value of $f_u$. Output the results modulo the given prime $M$.
Input
The first line contains three positive integers $n, k, M$.
Output
A single line containing $n$ numbers, representing the answers.
Examples
Input 1
3 1 1000000007
Output 1
3 500000005 1
Input 2
3 2 998244353
Output 2
9 499122179 1
Input 3
10 3 1000000007
Output 3
1000 225 333333416 500000039 714285737 523809537 357142865 83333337 777777785 1
Constraints
It is guaranteed that $1 \le n \le 10^5$, $1 \le k \le 200$, $10^8 \le M \le 10^9 + 7$, and $M$ is a prime number.
Subtasks
- subtask1(20pts): $n \le 10$.
- subtask2(20pts): $n \le 100$.
- subtask3(10pts): $k = 1$.
- subtask4(10pts): $k = 2$.
- subtask5(20pts): $k \le 20$.
- subtask6(20pts): No special properties.