Background

ZHY has many trees. Each tree has many nodes, and each node has a number on it, but he forgot what number was written on each node.

Problem Description

ZHY has $m$ trees. Every tree has the same shape and has $n$ nodes. Define $(i, j)$ as the $j$-th node on the $i$-th tree. You need to assign a value $a_{(i,j)}$ to every node $(i, j)$, and it must satisfy the following conditions:

• For all $\forall i \in [1,m],\forall j \in [1,n]$, we have $a_{(i,j)}\in\{0,1\}$.

• For all $\forall i \in [1,n]$, we have $\sum_{j=1}^m a_{(j,i)}\le 1$.

• For any edge $(u,v)$ and $i \in [1,m]$, we have $a_{(i,u)}+a_{(i,v)}\le 1$.

Please compute how many valid assignments there are, modulo $10^9+7$. Note that these $m$ trees are ordered.

Input Format

The first line contains two positive integers $n, m$.

The next $n-1$ lines each contain two positive integers $u, v$, indicating that in each of the $m$ trees there is an undirected edge between $u$ and $v$. It is guaranteed that the input forms a tree.

Output Format

Output one line containing the answer.

3 1
1 2
2 3

5

5 2
1 2
1 3
2 4
2 5

103

Hint

This problem uses bundled testdata.

For all testdata, $1 \le n \le 10^6$, $1 \le m \le 10^9$.

• Subtask 0 (10 pts): $n, m \le 4$.
• Subtask 1 (30 pts): $n, m \le 10^3$.
• Subtask 2 (15 pts): $n \le 10^3$.
• Subtask 3 (25 pts): $m = 1$.
• Subtask 4 (20 pts): No special constraints.

Translated by ChatGPT 5