Problem Statement

Takahashi loves trees and mountains. There is a tree with $N$ vertices, numbered from $1$ to $N$. It has $N-1$ edges, and the $i$-th edge connects vertex $a_i$ and vertex $b_i$. A "mountain" on this tree is a way of writing an integer between $1$ and $K$, inclusive, on each vertex that satisfies the following condition.

• There exists some $i\ (1\le i\le N)$ such that, for every $j\ (1\le j\le N,\ i\neq j)$, when traveling along the shortest path on the tree from vertex $i$ to vertex $j$, the sequence of integers written on the vertices passed through (including vertex $i$ and vertex $j$), arranged in order, is non-increasing. (*)

Input

$N\ K$
$a_1\ b_1$
$\vdots$
$a_{N-1}\ b_{N-1}$

All inputs are integers.
$2\le N,\ K \le 1000$
$1\le a_i, b_i\le N\ (1\le i\le N-1)$
The given graph is guaranteed to be a tree.

Output

Output the number of mountains modulo $10^9+7$.

Sample

3 2
1 2
2 3

7

6 3
1 2
2 3
2 4
1 5
5 6

188