由于原来的翻译大概是机翻，实在看不下去所以写一个人翻版本……（由于有了机翻所以没有提交翻译的通道了，只能发在讨论里）

题目描述

给出两个数 $n,p$，你需要求出下面四个问题的答案：

1. $n$ 个点的带标号无根树数量。
2. $n$ 个点的带标号有根树数量。
3. $n$ 个点的无标号有根树数量。
4. $n$ 个点的无标号无根树数量。

答案对 $p$ 取模。

输入格式

多组询问，每次询问给出 $n,p,k$，$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$ 为质数。

输出格式

对于每个询问，输出一行，包含一个整数表示答案。

## 题目描述
给出两个数 $n,p$，你需要求出下面四个问题的答案：
1. $n$ 个点的带标号无根树数量。
2. $n$ 个点的带标号有根树数量。
3. $n$ 个点的无标号有根树数量。
4. $n$ 个点的无标号无根树数量。

答案对 $p$ 取模。

## 输入格式
多组询问，每次询问给出 $n,p,k$，$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$ 为质数。

## 输出格式
对于每个询问，输出一行，包含一个整数表示答案。