問題文

アリの生息地として知られるパケンパークには、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. (1 点) K = 1
2. (1 点) K = N-1
3. (2 点) N \leq 15
4. (6 点) U_i = i , V_i = i+1 (1 \leq i \leq N-1)
5. (35 点) N \leq 2000, K \leq 5
6. (15 点) K \leq 5
7. (25 点) N \leq 10^5
8. (15 点) 追加の制約はない

入力例 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 の制約を満たします。