409862: GYM103811 F Furthest Travel

Flores has invented a new pre-programmed drone. The drone has to perform a trial mission in a cave of $$$N$$$ rooms numbered from $$$1$$$ to $$$N$$$. The cave has $$$N-1$$$ bidirectional corridors, each connecting two rooms, such that it is possible to visit between any rooms. In terms of graph theory, the rooms and corridors form a tree.

The mission is going to last for $$$T$$$ days, which can be represented as a sequence of $$$T+1$$$ rooms $$$r_0, r_1, r_2, \dots, r_T$$$. At the beginning of the first day, the drone shall start in any of the $$$N$$$ rooms, denoted as room $$$r_0$$$ in the sequence. On each of the $$$T$$$ days, the drone shall travel to the room furthest away from the room it starts, and stay in the destination room overnight. If there are more than one furthest room, the drone is allowed to reach any of them. The distance between two rooms is defined as the minimum number of corridors required to travel.

Formally:

• The drone can start in any room, denoted as $$$r_0$$$, at the beginning of day 1.
• On each day $$$i$$$ ($$$1\le i\le T$$$), the drone travels from room $$$r_{i-1}$$$ to $$$r_i$$$, where room $$$r_i$$$ is one of the furthest room from room $$$r_{i-1}$$$. The drone will stay in the room $$$r_i$$$ overnight.

Flores would like to know what is the number of possible sequences $$$r_0, r_1, \dots, r_T$$$ that satisfy all the requirements mentioned.

The first line contains a single integer $$$N$$$ ($$$2\le N\le 3000$$$).

The next $$$N-1$$$ line, each contains two integers $$$x$$$ and $$$y$$$, representing a corridor connecting room $$$x$$$ and room $$$y$$$ ($$$1\le x, y\le N$$$, $$$x\neq y$$$).

The last line contains a single integer $$$T$$$ ($$$1\le T\le 10^{18}$$$).

A single integer, the number of possible sequences $$$r_0, r_1, \dots, r_T$$$ that fulfill all the requirements mentioned. Please output the answer modulo $$$10^9+7$$$.

5
1 2
2 5
3 1
3 4
2

6

4
1 2
1 3
1 4
28

207959545

In the first sample, the $$$6$$$ possible sequences are $$$[1, 4, 5]$$$, $$$[1, 5, 4]$$$, $$$[2, 4, 5]$$$, $$$[3, 5, 4]$$$, $$$[4, 5, 4]$$$, $$$[5, 4, 5]$$$.

In the second sample, the answer is $$$1,207,959,552 \mod 1,000,000,007 = 207,959,545$$$.