SP1480 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$ 为质数。

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