SP1480 PT07D - Let us count 1 2 3

Given two integer _n_, _p_. 4 kinds of query is needed to solve: 1. Counting the number of labeled unrooted trees with _n_ nodes 2. Counting the number of labeled rooted trees with _n_ nodes 3. Counting the number of unlabeled rooted trees with _n_ nodes 4. Counting the number of unlabeled unrooted trees with _n_ nodes Calculate the answer modulo _p_.

Each line contains three integers _k_, _n_, _p_. _k_ denotes which kind of query this case is. For Kind 1 or Kind 2 query, 1

For each query, output a line which contains only one integer.