Wells

Time limit10sMemory limit1024 MB

Summary

Given a tree of N shelters, count the subsets of shelters with wells such that every simple path of exactly K shelters contains exactly one well, modulo 1e9+7.

Level: Medium7 of 10
Topics: Tree, Dynamic programming, DFS
Solved: No attempts yet

Problem

On the beautiful mountain of Velebit there are $N$ shelters. Exactly $N - 1$ pairs of shelters are connected by a hiking path, and it is possible to travel between any pair of shelters using these paths.

Vila the Fairy likes hiking very much. It takes her exactly one day to traverse a hiking path connecting two shelters. She can use her magical abilities to appear at any shelter at the beginning of a day, and then spend the next $K - 1$ days hiking without visiting the same shelter more than once. Thus, during each hike, Vila visits exactly $K$ shelters.

Vila gets thirsty while hiking, so she wants some shelters to have water wells. During every possible hike of hers, she wants to visit exactly one shelter with a well.

Determine whether a subset of shelters exists where wells can be placed to satisfy Vila's wishes. If so, count such subsets modulo $10^9 + 7$ .

Input

The first line contains two integers $N$ and $K$ ( $2 \le K \le N$ ).

The next $N - 1$ lines each contain two integers $a_i$ and $b_i$ ( $1 \le a_i, b_i \le N$ ), describing a hiking path between shelters $a_i$ and $b_i$ .

The given paths form a tree.

Output

On the first line, print YES if a subset of shelters satisfying Vila's conditions exists, and NO otherwise.

On the second line, print the number of such subsets modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
4 2
3 4
3 1
2 3
```
Expected output
```
YES
2
```
Example 2
Input
```
8 3
7 3
1 3
7 8
5 1
4 6
7 2
3 6
```
Expected output
```
NO
0
```
Example 3
Input
```
6 5
4 1
4 2
3 6
5 2
4 6
```
Expected output
```
YES
10
```