配点 : 100 点
問題文
帕肯公园被称为蚂蚁的栖息地,N 蚂蚁巢和 有 N-1 凹槽。在巢中 1, 2 \ldots N ,在凹槽中 1, 2 \ldots N-1 并按顺序编号。 i (1 \leq i \leq N-1) 是巢 U_i 和巢 V_i 双向连接。在这里,任何 2 两个巢通过多个凹槽在两个方向上连接。
生物学家帕肯先生发现,生活在帕肯公园的蚂蚁有以下习性。 生活在
- 巣 s (1 \leq s \leq N中的蚂蚁) s 和巢直接通过凹槽连接。 当且仅当有超过 K 块饼干时,从它们的巢中带入饼干。把它带进来后,窝 假设 s 中有一块饼干。请注意,此行为不会导致饼干从原来的巢中消失。
作为一个实验,帕肯先生决定选择几个巢穴,将饼干放入其中,最后调查有多少个巢穴含有饼干。N 来自最初放置饼干的巢。 1 如何选择多个窝 2^N-1 有多种方法可以做到这一点,但对于每种方法,找到饼干存在的最终巢数,并计算巢的总数。 P 求余数。
制約
- 1 \leq K \leq N \leq 10^6
- 10^8 \leq P \leq 10^9
- P 是质数
- 1 \leq U_i \lt V_i \leq N (1 \leq i \leq N-1)
- 给定的图是一棵树
- 所有输入均为整数
小課題
- (1 点) K = 1
- (1 点) K = N-1
- (2 点) N \leq 15
- (6 点) U_i = i , V_i = i+1 (1 \leq i \leq N-1)
- (35 点) N \leq 2000, K \leq 5
- (15 点) K \leq 5
- (25 点) N \leq 10^5
- (15 点)无附加约束
入力
输入将以以下形式通过标准输入给出。
N K P
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
出力
打印答案。
入力例 1
4 2 998244353 1 2 2 3 3 4
出力例 1
36
例如,先鸟巢 假设您将一块饼干放入 1, 3 中。然后,鸟巢 2 蚂蚁窝 1, 3 的 2 (\geq K) 把饼干从巢穴中拿出来。最后 巢中会有 1,2,3 的 3 饼干。
此示例是一个小作业。 满足 3, 4, 5, 6, 7 约束。
入力例 2
5 2 998244353 1 2 2 3 2 4 1 5
出力例 2
93
此示例是一个小作业。 满足 3, 5, 6, 7 约束。
入力例 3
5 1 998244353 1 2 2 3 2 4 1 5
出力例 3
155
此示例是一个小作业。 满足 1, 3, 5, 6, 7 约束。
入力例 4
5 4 998244353 1 2 1 3 1 4 1 5
出力例 4
81
此示例是一个小作业。 满足 2, 3, 5, 6, 7 约束。
入力例 5
15 2 998244353 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15
出力例 5
312049
此示例是一个小作业。 满足 3, 5, 6, 7 约束。