200% 190% 180% 170% 160% 150% 140% 130% 120% 110% 100%

Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

acm

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

cz

ˇ

University of Zilina

Masaryk University

Matej Bel University in Bansk´ Bystrica

a

University of West Bohemia

CTU Open Contest 2016

Tree Stands

huntsmen.c, huntsmen.cpp, huntsmen.c11, Huntsmen.java, huntsmen.py

Tree stands are elevated wooden platforms attached to trees. Typically, huntsmen use tree

stands to watch or to shoot their prey.

In our county, huntsmen have built a remarkable system of tree stands. The tree stands are

connected by narrow straight paths which form a kind of maze on the hunting grounds. The

builders wanted to minimize the impact on the environment and so they built the minimum

possible number of paths which ensure that there is a connection between any two tree stands.

Also, a tree stand is visible from another stand if and only if the two are connected by a path.

A group of local huntsmen wants to find out which particular tree stands will serve the best

their hunting interests. Each day they climb a different set of tree stands and watch the wildlife.

There are a few more important circumstances to consider:

· Security rules dictate that any occupied tree stand must be visible from at least one other

occupied tree stand so that in case of an emergency the huntsman in the neighbour tree

stand can come to help the colleague.

· A tree stand is always occupied by at most one huntsman.

· It does not matter which huntsman is in which tree stand. It only matters which tree

stands are occupied and which are not.

· The size of the group does not change.

How many days will the group spend in the tree stands before they investigate all possible

choices of tree stands available to them?

Input Specification

There are more test cases. Each case starts with a line containing two integers N and K

(2 ≤ K ≤ N ≤ 200) separated by space. N is the number of tree stands, K is the size of the

group of huntsmen. The tree stands are labeled 1, 2, 3, . . . , N .

Next, there are N - 1 lines, each line specifies one path between two tree stands. The line

contains the labels of the stands separated by a space. The order of the labels on a line and the

order of the paths in the input is arbitrary.

Output Specification

For each test case, print on a separate line the number of days which the group will spend in

the tree stands. Express the result modulo 1 000 000 007.

Sample Input

4

3

1

2

1

4

1

3

5

4

1

2

2

3

3

4

4

5

Output for Sample Input

3

3