Trees
题目背景
ZHY 有很多树,每个树上都有很多点,每个点上都有一个数,但他忘记了每个点上写的数是什么了。
题目描述
ZHY 拥有 $m$ 棵树,每棵树形态相同,且均有 $n$ 个点。定义 $(i,j)$ 是第 $i$ 棵树上的第 $j$ 个点,你需要为每个点 $(i,j)$ 赋一个值 $a_{(i,j)}$,且满足以下条件:
- 对于 $\forall i \in [1,m],\forall j \in [1,n]$,有 $a_{(i,j)}\in\{0,1\}$。
- 对于 $\forall i \in [1,n]$,有 $\sum_{j=1}^m a_{(j,i)}\le 1$。
- 对于任意的一条边 $(u,v)$ 和 $i \in [1,m]$,有 $a_{(i,u)}+a_{(i,v)}\le 1$。
请你计算有多少种赋值方式,对 $10^9+7$ 取模。注意这 $m$ 棵树是有序的。
输入输出格式
输入格式
第一行两个正整数 $n,m$。
接下来 $n-1$ 行,每行两个正整数 $u,v$,表示这 $m$ 棵树中每棵树都有一条从 $u$ 到 $v$ 的无向边。保证数据可以构成一棵树。
输出格式
输出一行表示答案。
输入输出样例
输入样例 #1
3 1
1 2
2 3
输出样例 #1
5
输入样例 #2
5 2
1 2
1 3
2 4
2 5
输出样例 #2
103
说明
**本题使用捆绑数据。**
对于所有的数据,$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):无特殊限制。