Original Inspiration

Problem Statement

There is a tree with $N$ vertices. The vertices are numbered from $1$ to $N$, and the $i$-th edge connects vertex $a_i$ and vertex $b_i$.

Takahashi, who loves $3$, is looking for sequences $p_1,p_2,\dots,p_N(1 \le p_i \le C)$ consisting of integers from $1$ to $C$ that satisfy the following condition.

• For every pair of adjacent vertices $(i,j)$, $|p_i-p_j|=3$

For Takahashi, find the number of sequences satisfying the condition, modulo $10^9+7$.

Constraints

• $2 \le N \le 1000$
• $1 \le a_i,b_i \le N$
• $4 \le C \le 10^9$
• The given graph is a tree

Input

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

Line $1$ contains $N,C$ separated by a space.
Line $i+1(1\le i \le N-1)$ contains $a_i,b_i$ separated by a space.

Output

Print the number of sequences modulo $10^9+7$ on 1 line.
Print a newline at the end.

Sample

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