Star Trek

The United Federation of Planets is an alliance of $N$ planets, numbered from $1$ to $N$. Some planets are connected by space tunnels. A starship can fly through a space tunnel in both directions very fast. There are exactly $N-1$ space tunnels, and any planet in the Federation can reach any other planet through them.

There are $D$ additional parallel universes. Each one is an exact copy of our universe, with the same planets and space tunnels. They are numbered from $1$ to $D$, and our universe is number $0$. Planet $x$ in universe $i$ is written $P^i_x$. Travel between universes uses dimension portals. For every $i$ ($0 \le i \le D-1$), exactly one portal is placed that flies from $P^i_{A_i}$ to $P^i_{B_i}$, where $1 \le A_i, B_i \le N$.

After all portals are placed, the starship Batthyány begins its maiden voyage, orbiting $P^0_1$. Captain Ágnes and Lieutenant Gábor play a game. They take turns choosing a destination planet. The destination can be in the same universe if a space tunnel leads there, or in another universe if a portal leads there. Their goal is to visit places where nobody has gone before. Once a planet $P^i_x$ has been visited, neither of them goes back there, though planet $x$ in another universe may still be visited. Captain Ágnes picks first, then Gábor, then Ágnes again. A player who cannot pick an unvisited planet on their turn loses.

Both players know the locations of all tunnels and portals, and both play optimally. For how many different portal placements does Captain Ágnes win? Two placements differ if, for some index $i$ ($0 \le i \le D-1$), the $i$th portal connects a different pair of planets in the two placements, that is, $A_i$ or $B_i$ differs. Give the answer modulo $10^9+7$.

The first line contains two integers $N$ and $D$. Each of the next $N-1$ lines contains two integers $u$ and $v$, meaning that $P^i_u$ and $P^i_v$ are connected by a space tunnel for every $i$ ($0 \le i \le D$).

Print one integer: the number of portal placements where Captain Ágnes wins, modulo $10^9+7$.

$2 \le N \le 10^5$

$1 \le D \le 10^{18}$

$1 \le u, v \le N$

There is only 1 portal, so there are $3 \times 3 = 9$ different placements. The following 4 placements are the ones where the Captain wins.