You are given a rooted tree of $N$ nodes. Each node is numbered from $1$ to $N$ and the value associated with that node is the node number itself. Additionally, you are also given an integer $K$. Now for every node of the tree, you can choose any combination of exactly $K$ size of its children. Each combination is equally probable. The special value of a node is denoted by the sum of node values involved in the combination of children chosen. You need to calculate the expected special value of each node in the tree. If there are less than $K$ children of that node, then expected special value is $0$.
Note: $1$ is the root node of the tree.

Input
The first line contains an integer $N$ and $K$ as input.
The next $N - 1$ lines contain a pair of integers $u,v$ as input that denotes that there is an edge between the nodes $u$ and $v$.

Output
In the output, you need to print the expected special value of each node modulo $1000000007$.

Constraints
$1 \le N \le 10^5\\ 1 \le K \le 10^5$