JAPLJの住む町にある植物園では広大な土地に様々な花が植えられている。この植物園には全部で N 種類の花があり、1から N までの番号がつけられている。それぞれの種類の花はひとつの場所にまとめて植えられており、花 f がまとめて植えられている場所を花 f のエリアと呼ぶ。
この植物園では客がエリアを見て回るために、エリアとエリアの間にいくつかの道を敷設している。ひとつの道は2つの異なるエリアを結んでおり、双方向に通行可能である。現在、どのエリアからどのエリアへも道を辿って行くことができ、かつその経路は1通りしかない。すなわちエリア間のネットワークは木構造を成しており、道はちょうど N-1 本ある。この状態では客が全てのエリアを見て回るのにあまりに多くの時間がかかると植物園は考えたため、新たに道を最大で K 本敷設することになった。
新たに敷設する道も既存の道と同じく、2つの異なるエリアを結んでいて双方向に通行可能なものであるとする。既にひとつの道でつながれている2つのエリアを結ぶ道を敷設することは可能だが、あるエリアから出て同じエリアに入るような道を敷設することはできない。また、道をいくつか新たに敷設することでちょうど K 個の周遊路ができるようにしたい。ここで周遊路とは、あるエリアから出発して、同じ道を1度しか通らずに元のエリアへ返ってくるような経路のことである。その K 個の周遊路はエリアを共有してはならない。すなわち、あるひとつのエリアが2つ以上の周遊路に含まれるようなことがあってはならない。
次に敷設の例を示す。植物園のエリアが図1のように繋がっているとしよう。また、K = 2 であるとする。このとき、図2および図3のように新たな道を敷設することを考える。新たに敷設された道は赤く示してある。また、周遊路を構成する道は黄色く示してある。図2のような方法は条件を満たしているが、図3のような方法では赤く示されたエリア(この場合は1,2,3,5,6)が2つ以上の周遊路の両方に含まれており、また周遊路が2つより多く存在するため条件を満たしていない。
さて、植物園は以上の条件を満たすような新たな道の敷設方法について最善なものを探したい。そのためにまず植物園は以上の条件を満たすような新たな道の敷設方法は何通りあるか知りたがっている。その値は非常に大きくなるかもしれないので、その値を与えられた整数 M で割ったあまりを求めるだけでよい。そのためのプログラムを作成せよ。
入力の最初の1行には3つの整数 N (N >= 2), K (K >= 1), M (2 <= M <= 1000000007 < 230) が書かれている。 N は植物園のエリア数、 K は新たに敷設する道の総数を表している。 M の値は計算を簡素にするためのもので特別な意味はないことを注意しておく。後に N-1 行の入力が続く。
続く行には既に敷設されている道の情報が書かれている。各行には2つの整数 A, B (1 <= A, B <= N, A ≠ B) が書かれている。これは花 A のエリアと花 B のエリアを直接結ぶ道が存在することを表す。
1行出力せよ。その1行には問題文中の条件を満たす新たな道路の敷設方法の総数を M で割ったあまりが書かれていなければならない。
採点用データはいくつかのテストグループからなる。
このテストグループでは、与えられる木は分岐しておらず、エリアは一直線に繋がっている。すなわち、N 個のエリアのうち 2 個からは道が1本だけ出ており、残りの N-2 個からは2本の道が出ている。また、N <= 100000, K <= 10 である。
このテストグループでは N <= 10, K <= 10 である。
このテストグループでは N <= 1000, K <= 2 である。
このテストグループでは N <= 100000, K <= 2 である。
このテストグループでは、あるエリアと直接道で繋がっているエリアの数は10以下である。また、N <= 1000, K <= 10 である。
このテストグループでは N <= 100000, K <= 10 である。
7 2 11 1 2 1 3 2 4 3 5 3 6 4 7
9
10 3 100 9 6 7 2 4 8 1 2 2 6 5 6 6 8 10 8 3 8
54
サンプル入力1は問題文中の画像に対応している。この場合、敷設の方法は全部で 31 通りあるので、それを与えられた数 11 で割ったあまりである 9 を出力する。