Description

给定一棵以 $1$ 为根的有根树，定义树的一个毒瘤集为一个集合，并且集合中任意两个元素之间不存在祖先与后代关系。

定义一个毒瘤集的毒瘤指数为集合内所有元素的价值之和。要求给定树的所有毒瘤集的毒瘤指数之和，答案对 $100{,}000{,}007$ 取模。

但这个问题太难了，所以我们考虑化简。

因为点的编号跟它毒瘤指数密切相关，所以我们将会再给出一个整数 $T$：$T = 1$ 表示 $i$ 号点的毒瘤指数为 $i$；$T = 0$，表示所有点的毒瘤指数都是 $1$。

Input Format

第一行两个整数 $n$、$T$，表示这棵树有 $n$ 个节点。

接下来 $n -1$ 行，每行两个整数 $x$ 和 $y$，表示有一条边，连接 $x$ 和 $y$。

Output Format

输出一个整数，表示答案。

5 0
1 2
2 3
2 4
1 5

16

Hint

样例解释：

$10$ 个集合分别为 $\{1\},\{2\},\{3\},\{4\},\{5\},\{2,5\},\{3,4\}, \{3,5\},\{3,4,5\},\{4,5\}$

数据范围与约定

本题采用多测试点捆绑测试

• 对于 $30 \%$ 的部分分，$n \le 15$；
• 另外 $20 \%$ 的部分分，$n \le 10^6$，$T = 0$；
• 对于 $100 \%$ 的数据，$n \le 10^6$，$T <= 1$。

为了方便你理解题意，下面给出毒瘤集的数学定义：

设一个毒瘤集为 $A$，则

• $\forall i\in A$，不存在一个点 $j$，使得 $j$ 在从 $i$ 到根节点的简单路径上，且 $j \in A$。其中 $i,j \in V$，$V$ 为树的点集。