Description

The aliens are attacking Earth yet again, and the alien mothership is already en route to Earth. This time, JYY has contacted the Golden Fleet and plans to unite all JSOIer to resist the alien invasion.

Before the Golden Fleet takes position, JYY intends to first learn the aliens' plan. Now, an agent carrying listening devices has secretly infiltrated the alien mothership to eavesdrop on their communications.

The alien mothership can be regarded as an undirected tree with $n$ nodes and $n-1$ edges. The nodes on the tree are numbered $1,2,\cdots,n$. The agent employed by JYY is equipped with a stealth module, allowing free movement within the mothership and the ability to install listening devices on nodes without being detected.

If a listening device is installed at node $u$, then JYY can monitor the communications of all nodes directly adjacent to $u$. In other words, if a device is placed at node $u$, then for every edge $(u,v)$ in the tree, node $v$ will be monitored. Note in particular that a device placed at node $u$ does not monitor the communications of $u$ itself; this is a tactic designed by JYY to avoid detection by the aliens.

The agent carries exactly $k$ listening devices. JYY wants to know how many different ways there are to place the devices so that the communications of all nodes on the mothership are monitored. To avoid waste, at most one device may be installed on each node, and all devices must be used.

Input Format

The first line of input contains two integers $n,k$, representing the number of nodes $n$ of the mothership and the number of listening devices $k$. The next $n-1$ lines each contain two integers $u,v$ $(1\le u,v\le n)$, representing an edge in the tree.

Output Format

Output a single line containing the number of valid configurations. Since the answer may be large, you only need to output the remainder $\text{mod 1,000,000,007}$.

5 3
1 2
2 3
3 4
4 5

1

Hint

Explanation for Sample 1

The sample is a chain $1-2-3-4-5$. First, nodes $2$ and $4$ must have devices; otherwise $1$ and $5$ cannot be monitored (a device does not monitor the node it sits on). The remaining device must be placed on node $3$ to monitor both $2$ and $4$. Therefore, placing devices on nodes $2,3,4$ is the only valid configuration.

Constraints

• For $10\%$ of the testdata, $1 \le n \le 20$.
• For another $10\%$ of the testdata, $1 \le n \le 100$.
• For another $10\%$ of the testdata, $1 \le k \le 10$.
• For another $10\%$ of the testdata, the input tree is a chain.
• For all testdata, $1\le n\le 10^5$, $1\le k\le \min\{n,100\}$.

Translated by ChatGPT 5