F. Furthest Travel
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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}$$$).

Output

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$$$.

Examples
Input
5
1 2
2 5
3 1
3 4
2
Output
6
Input
4
1 2
1 3
1 4
28
Output
207959545
Note

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$$$.