AT_pakencamp_2024_day2_b Biscuit and Ants

アリの生息地として知られるパケンパークには、 $ 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 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ P $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_{N-1} $ $ V_{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 $ 点) 追加の制約はない ### Sample Explanation 1 例えば、最初に巣 $ 1, 3 $ にビスケットを投入したとします。すると、巣 $ 2 $ のアリは巣 $ 1, 3 $ の $ 2 (\geq K) $ 個の巣からビスケットを運び出します。最終的には $ 1,2,3 $ の $ 3 $ 個の巣にビスケットが存在することになります。 このサンプルは小課題 $ 3, 4, 5, 6, 7 $ の制約を満たします。 ### Sample Explanation 2 このサンプルは小課題 $ 3, 5, 6, 7 $ の制約を満たします。 ### Sample Explanation 3 このサンプルは小課題 $ 1, 3, 5, 6, 7 $ の制約を満たします。 ### Sample Explanation 4 このサンプルは小課題 $ 2, 3, 5, 6, 7 $ の制約を満たします。 ### Sample Explanation 5 このサンプルは小課題 $ 3, 5, 6, 7 $ の制約を満たします。 ### Constraints - $ 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 $ ) - 与えられるグラフは木である - 入力は全て整数