#1280. PT07D - Let us count 1 2 3

PT07D - Let us count 1 2 3

题目描述

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

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

答案对 pp 取模。

输入格式

多组询问,每次询问给出 k,n,pk,n,p, nn 是点数, pp 是模数, kk 是第几种询问。

对于第 1,21,2 种询问, 1≤n≤1091\leq n\leq 10^9。

对于第 3,43,4 种询问, 1≤n≤103,n≤p1\leq n\leq 10^3,n\leq p。

对于所有询问,保证 2≤p≤1042\leq p \leq 10^4 且 pp 为质数。

输出格式

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

样例

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

题目来源:洛谷 SP1480