题目内容

给定一棵有 $n$ 个节点的无向连通无环图(树)。节点编号为 $1$ ~ $n$ 。你需要恰好删除 $k$ 条边，将原树分成上 $k+1$ 个连通块。要求所有连通块的节点数量均为偶数。

请你计算满足条件的删除方案总数，并对 $10^9+7$ 取模输出。

【名词解释】

• 树：树 是一个无向、连通且无环的图结构。

• 连通块：连通块 指图中任意两点间均存在路径的极大顶点集合。

输入描述

第一行输入两个整数 $n$ 和 $k(1 ≦n≦2×10^5,0≦k≦n-1)$ ，分别表示树的节点数量和要删除的边数。

接下来 $n -1$ 行，每行输入两个整数 $u_i,v_i(1≦u_i,v_i≦n,u_i≠v_i)$，表示一条边连接节点 $u_i$ 与 $v_i$ 。输入保证构成一棵树。

输出描述

输出一个整数，表示删除恰好 $k$ 条边后，使得所有连通块节点数均为偶数的方案总数，对 $10^9+7$ 取模。

样例1

输入

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

输出

3

样例2

输入

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

输出

3