P9161 Trees

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.

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.

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 one line containing the answer.

**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