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

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

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

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

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

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

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

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。

luogu