题目描述

题目译自 CEOI 2021 Day2 T3「Wells」

美丽的韦莱比特山上有 $N$ 座山间小屋，恰好 $N-1$ 对小屋被一条徒步行道连接，并且使用这些道路，可以从任意一间小屋到达任意另一间小屋。

小精灵 Vila 十分喜欢徒步旅行，通过连接两个小屋的一条道路恰好会花费她一天的时间。她可以使用魔法，让她某天开始在任一小屋处出现，然后花费剩下的 $K-1$ 天进行徒步旅行，在旅行中她不会经过相同的小屋超过一次。因此在她的旅行中，Vila 恰好经过了 $K$ 间小屋。

Vila 在徒步旅行中会很渴，所以她希望一些小屋有水井。在她进行的任何可能的旅行中，她想要经过恰好一个有水井的小屋。

你的任务是确定是否可以找到小屋的一个子集放置水井，满足 Vila 这个奇怪的愿望。此外，你需要计算满足条件的子集数对 $10^9+7$ 的值。

形式化地说，给定一棵 $N$ 个节点的树和一个正整数 $K$，确定是否存在一个点集，满足任意树上恰好包含 $K$ 个点的路径上都恰好有一个点在这个点集中。此外，你需要求出这样的子集个数，对 $10^9+7$ 取模。

输入格式

第一行包含两个整数 $N$ 和 $K\ (2\le K\le N)$，意义如题目描述。

接下来 $N-1$ 行描述徒步行道。第 $i$ 行包含两个空格隔开的整数 $a_i$ 和 $b_i\ (1\le a_i,b_i\le N)$，表示一条连接 $a_i$ 和 $b_i$ 的徒步行道。

输入保证这些道路形成了一棵树。

输出格式

如果存在这样的满足 Vila 要求的小屋子集，第一行输出 YES，否则第一行输出 NO。

第二行输出满足 Vila 要求的小屋子集个数，对 $10^9+7$ 取模。

4 2
3 4
3 1
2 3

YES
2

8 3
7 3
1 3
7 8
5 1
4 6
7 2
3 6

NO
0

6 5
4 1
4 2
3 6
5 2
4 6

YES
10

数据范围与提示

如果你的程序第一行输出正确，但是第二行没有输出正确答案，那么你会获得这部分测试点 $60\%$ 的分数。

每个子任务的得分等于子任务中测试点的最低得分。