Background

DDOSvoid has recently been very obsessed with tree structures, especially the “persistent Pleasant Goat and Big Big Wolf set Red Wolf tree”, which can maintain any information you want in $O(\log)$ time.

However, this is only a theoretical data structure. In order to study how it can be implemented, DDOSvoid began to think about the relationship between a tree’s parent and children.

If this data structure could be implemented, then there would be no more nasty problems in this world.

But after all, this problem is too hard, so let us first consider the following problem.

Problem Description

Given a rooted tree with root $1$, define a “nasty set” of the tree as a set such that for any two elements in the set, there is no ancestor-descendant relationship between them.

Define the “nasty index” of a nasty set as the sum of the values of all elements in the set. You are asked to compute the sum of the nasty indices of all nasty sets of the given tree, modulo $100{,}000{,}007$.

But this problem is too hard, so we consider a simplified version.

Because the node numbering is closely related to its nasty index, we will additionally give an integer $T$: when $T = 1$, the value (nasty index contribution) of node $i$ is $i$; when $T = 0$, the value of every node is $1$.

Input Format

The first line contains two integers $n$ and $T$, meaning the tree has $n$ nodes.

The next $n - 1$ lines each contain two integers $x$ and $y$, meaning there is an edge connecting $x$ and $y$.

Output Format

Output one integer, the answer.

5 0
1 2
2 3
2 4
1 5

16

Hint

Sample Explanation:

The $10$ sets are $\{1\},\{2\},\{3\},\{4\},\{5\},\{2,5\},\{3,4\}, \{3,5\},\{3,4,5\},\{4,5\}$.

Constraints and Notes

This problem uses bundled multiple test points.

• For $30\%$ of the points, $n \le 15$.
• For another $20\%$ of the points, $n \le 10^6$, $T = 0$.
• For $100\%$ of the data, $n \le 10^6$, $T \le 1$.

To help you understand the statement, here is the mathematical definition of a nasty set:

Let a nasty set be $A$. Then:

• $\forall i\in A$, there does not exist a node $j$ such that $j$ lies on the simple path from $i$ to the root, and $j \in A$. Here $i, j \in V$, and $V$ is the vertex set of the tree.

Translated by ChatGPT 5