A. Tree Orientation
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

There are different legends for tasks. They can be long or short. They can be boring or funny. They can be understandable or not. You decide: what is this.

Given an undirected tree with n vertices. Find out how many different ways you can orient the edges of the tree so that the result graph will contain exactly m sink vertices. Sink vertex is a vertex with zero outdegree.

Input

The first line of input contains two numbers n (the total number of vertices) and m (required number of sink vertices).

Each of the following n - 1 rows contains a description of the edges, i.e. its ends ui and vi.

1 ≤ n ≤ 1000
0 ≤ m ≤ n
1 ≤ ui, vi ≤ n
Output

You should output an amount of ways to orient the tree modulo 109 + 7.

Example
Input
5 2
1 2
2 3
3 4
3 5
Output
8