P6803 [CEOI 2020] Star Trek.

Original time limit: 0.2 s, 32 MB.

The Interstellar Federation consists of $N$ planets, numbered $1 \sim N$. Some planets are connected by interstellar passages. Through these passages, a spaceship can travel back and forth between planets in a short time. There are exactly $N-1$ interstellar passages in the whole federation, and using these passages, it is possible to travel between any two planets. Besides our universe, there are $D$ parallel universes. These parallel universes are exact copies of our universe: their planets and interstellar passages are exactly the same as ours. We number these parallel universes as $1 \sim D$ (our universe is numbered $0$), and denote the $x$-th planet in the $i$-th universe by $P_{x}^i$. Using stargates, we can travel among these parallel universes. For all $i \in [0,D)$, we will choose one $A_i$ and one $B_i$ (with $1 \leq A_i,B_i \leq N$), and build a **one-way** (only from $P_{A_i}^i$ to $P_{B_i}^{i+1}$) stargate between $P_{A_i}^i$ and $P_{B_i}^{i+1}$. After all stargates are ready, the Federation starship Batthyány will start its maiden voyage. It is currently orbiting planet $P_1^0$. Captain Ágnes plans to play the following game with Lieutenant Gábor: the two players alternately choose the next destination of the starship, and the destination must be directly reachable via an interstellar passage or a stargate. They want each visited planet to be one that has not been visited before. That is, if the starship arrives at $P_{x}^i$, then they will never pass through that planet again (but they may still arrive at the corresponding planet $x$ in other parallel universes). Captain Ágnes moves first, Lieutenant Gábor moves second. If a player, on their turn, cannot choose a legal destination, then that player loses the game. Both the captain and the lieutenant are perfectly smart. They know the full layout of all interstellar passages and stargates, and they always play optimally. You need to find how many stargate layouts make Captain Ágnes (the first player) guaranteed to win. Two stargate layouts are different if and only if there exists an integer $i$ such that $A_i$ or $B_i$ is different.

The first line contains two integers $N,D$, representing the number of planets in the federation and the number of parallel universes. The next $N-1$ lines each contain two integers $u,v$, meaning that for all $i \in [0,D]$, there is an interstellar passage connecting $P_u^i$ and $P_v^i$.

Output the number of stargate layouts that make the captain guaranteed to win, modulo $10^9+7$.

### Sample Explanation There are $3 \times 3=9$ essentially different stargate layouts in total. Four winning cases for the captain are listed below.  ### Subtasks All testdata satisfy: $1 \leq N \leq 10^5$, $1 \leq D \leq 10^{18}$, $1 \leq u,v \leq N$. The constraints for each subtask are as follows: | Subtask ID | Points | Constraints | | ---------- | ------ | -------------------------------- | | $1$ | $0$ | Sample | | $2$ | $7$ | $N=2$ | | $3$ | $8$ | $N \leq 100$，$D=1$ | | $4$ | $15$ | $N \leq 1000$，$D=1$ | | $5$ | $15$ | $D=1$ | | $6$ | $20$ | $N \leq 1000$，$D \leq 10^5$ | | $7$ | $20$ | $D \leq 10^5$ | | $8$ | $15$ | No special constraints. | Translated by ChatGPT 5