PT07D - Let us count 1 2 3

## 题目描述 给出两个数 $n,p$，你需要求出下面四个问题的答案： 1. $n$ 个点的带标号无根树数量。 2. $n$ 个点的带标号有根树数量。 3. $n$ 个点的无标号有根树数量。 4. $n$ 个点的无标号无根树数量。 答案对 $p$ 取模。 ## 输入格式 多组询问，每次询问给出 $k,n,p$， $n$ 是点数， $p$ 是模数， $k$ 是第几种询问。 对于第 $1,2$ 种询问， $1\leq n\leq 10^9$。 对于第 $3,4$ 种询问， $1\leq n\leq 10^3,n\leq p$。 对于所有询问，保证 $2\leq p \leq 10^4$ 且 $p$ 为质数。 ## 输出格式 对于每个询问，输出一行，包含一个整数表示答案。

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 <= _n_ <= 10 $ ^{9} $ . For Kind 3 or Kind 4 query, 1 <= _n_ <= 10 $ ^{3} $ and _n_ <= _p_. For all queries, 2 <= _p_ <= 10 $ ^{4} $ and _p_ is a prime.

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

1 2 2
2 2 3
3 2 5
4 2 3

1
2
1
1