The alien mothership can be viewed as an undirected tree with $n$ nodes and $n-1$ edges, where the nodes are labeled $1, 2, \dots, n$. JYY's agents are equipped with stealth modules, allowing them to move freely within the alien mothership and install monitoring devices on nodes without being detected.

If a monitoring device is installed on node $u$, JYY can monitor the communication of all nodes directly adjacent to $u$. In other words, if a monitoring device is installed on node $u$, then for every edge $(u, v)$ in the tree, node $v$ will be monitored. Note specifically that a monitoring device placed on node $u$ does not monitor the communication of $u$ itself; this is a tactic JYY specifically uses to prevent the aliens from discovering the deployment.

JYY's agents carry a total of $k$ monitoring devices. JYY wants to know how many different ways there are to place the monitoring devices such that the communication of all nodes on the mothership is monitored. To avoid waste, at most one monitoring device can be installed on each node.

Input

The first line contains two integers $n$ and $k$, representing the number of nodes in the mothership and the number of monitoring devices, respectively.

The next $n-1$ lines each contain two integers $u, v$ ($1 \le u, v \le n$), representing an edge in the tree.

Output

Output a single line representing the number of valid configurations. Since the answer may be very large, you only need to output the answer modulo $1,000,000,007$.

Examples

Input 1

5 3
1 2
2 3
3 4
4 5

Output 1

1

Note

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

Constraints

• $10\%$ of the data satisfies $1 \le n \le 20$;
• Another $10\%$ of the data satisfies $1 \le n \le 100$;
• Another $10\%$ of the data satisfies $1 \le k \le 10$;
• Another $10\%$ of the data guarantees the tree is a chain;
• For all data, $1 \le n \le 10^5$, $1 \le k \le \min\{n, 100\}$.