405830: GYM102133 A Tree Orientation

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.

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 u_i and v_i.

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

5 2
1 2
2 3
3 4
3 5

8