Counting Valid Tree Assignments

ZHY has (m) trees, each with (n) nodes. The trees all share the same structure. We label the nodes on each tree as ((i,j)) where (i) ((1 \le i \le m)) is the tree index and (j) ((1 \le j \le n)) is the node index within that tree. You need to assign a value (a_{(i,j)}) to each node satisfying the following conditions:

1. For every tree (i) and every node (j), (a_{(i,j)} \in {0,1}).

2. For every node index (j) (that is, the (j)th node in each tree), at most one tree can have a value of 1, i.e., (\sum_{i=1}^{m} a_{(i,j)} \le 1) for all (j \in [1,n]).

3. For every tree (i) and every edge ((u,v)) in the tree, we must have (a_{(i,u)}+a_{(i,v)} \le 1). In other words, in every tree, the set of nodes with value 1 forms an independent set.

Your task is to calculate the number of valid assignments modulo (10^9+7). Note that the (m) trees are ordered.

Explanation

The problem can be reformulated in the following way. For each tree, a valid assignment is equivalent to selecting an independent set of nodes (possibly empty). The additional vertical condition (condition 2) ensures that for every node index \(j\) (which is common across all trees), at most one tree selects that node. We can view this as assigning each node index a value from \(\{0,1,2,\dots,m\}\), where 0 means that none of the trees has chosen that node, and a nonzero value \(i\) means that exactly the \(i\)th tree picks that node. However, note that within a tree, the chosen nodes must form an independent set (because of condition 3).

A standard tree dynamic programming approach can be applied by rooting the tree (say, at node 1) and computing for each node two values:

• (f(u,0)): the number of ways to label the subtree of (u) if node (u) is not selected (i.e. assigned 0),
• (f(u,1)): the number of ways to label the subtree of (u) if node (u) is selected (i.e. assigned a fixed nonzero value).

When a node is not selected, each child can either be not selected (contributing (f(child,0))) or selected (in any of the (m) trees, contributing (m, f(child,1))). When a node is selected (with a fixed nonzero label), each child can be either not selected or selected in one of the other (m-1) ways (to ensure that the same index is not used in both parent and child).

Thus, if we let (f(u,0)=\prod_{v \in child(u)}\Bigl(f(v,0)+m, f(v,1)\Bigr)) and (f(u,1)=\prod_{v \in child(u)}\Bigl(f(v,0)+(m-1), f(v,1)\Bigr)), then the answer for the entire tree is given by [ \text{ans} = f(\text{root},0) + m \cdot f(\text{root},1) \pmod{10^9+7}. ]

The input provides the integers (m) and (n) on the first line, followed by (n-1) lines each containing two integers (u) and (v) that describe an edge of the tree (the same tree structure applies to each of the (m) trees).

inputFormat

The first line contains two integers \(m\) and \(n\) \((1 \le m, n \le 10^5)\), where \(m\) is the number of trees and \(n\) is the number of nodes in each tree.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) \((1 \le u, v \le n)\) representing an edge of the tree.

outputFormat

Output a single integer representing the number of valid assignments, modulo \(10^9+7\).

sample

2 1

3