元ネタ

問題文

$N$ 頂点の木があります。頂点には $1$ から $N$ までの番号がついており、$i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

$3$ が大好きな高橋くんは、以下の条件を満たす $1$ から $C$ までの整数からなる数列 $p_1,p_2,\dots,p_N(1 \le p_i \le C)$ を探しています。

• 隣り合う頂点の組 $(i,j)$ について、$|p_i-p_j|=3$

高橋くんのために条件を満たす数列の個数を $10^9+7$ で割った余りを求めてください。

制約

• $2 \le N \le 1000$
• $1 \le a_i,b_i \le N$
• $4 \le C \le 10^9$
• 与えられるグラフは木である

入力

$N\ C$
$a_1\ \ b_1$
$a_2\ \ b_2$
$\vdots$
$a_{N-1}\ \ b_{N-1}$

$1$ 行目には $N,C$ が空白区切りで与えられる。
$i+1(1\le i \le N-1)$ 行目には $a_i,b_i$ が空白区切りで与えられる。

出力

数列の個数を $10^9+7$ で割った余りを1行に出力してください。
最後に改行してください。

サンプル

5 4
1 2
1 3
3 4
3 5

2

5 5
1 2
1 3
3 4
3 5

4

5 7
1 2
1 3
3 4
3 5

16