405717: GYM102055 D Cube

Mr. Panda and his friends are trapped in a maze of $$$N$$$ rooms. Rooms are connected by bidirectional doors and the maze happens to be a tree (i.e. there is no cycle of rooms in the maze). Each room has an assigned value $$$v_i$$$ to it.

With some exploration inside the maze, Mr. Panda find out that a room can only be entered at most twice. After a room has been entered twice, the room's deadly trap will be activated and it's no longer safe to enter that room. Note that the room where Mr. Panda starts the exploration is considered being entered once at the beginning.

Mr. Panda and his friends are initially at room $$$S$$$. As they have no clue on how to escape the maze, they decide to move randomly. At each step, they pick the next room with equal probability among all adjacent rooms that are still safe. They keep moving from room to room until they are stuck at some room, i.e. there is no safe next room from the that room.

As an algorithm geek, Mr. Panda wonders what's the expected value of the last room.

The first line of the input gives the number of test cases, $$$T$$$ ($$$1 \le T \le 10$$$). $$$T$$$ test cases follow.

For each test case, the first line contains an integers $$$N$$$ ($$$1 \le N \le 10^{5}$$$) representing the number of rooms. The next line contains $$$N$$$ integers $$$v_1, v_2, \ldots, v_N$$$ ($$$0 \le v_i \le 1000$$$) representing the assigned value for each room.

The next $$$N-1$$$ lines each contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le N$$$), describing the edges of the maze.

The last line contain an integer $$$S$$$ ($$$1 \le S \le N$$$) representing the initial room number.

For each test case, output one line containing "Case x: y", where x is the test case number (starting from $$$1$$$) and y is the expected value of the last room. The expected value y can be written as a reduced fraction $$$p / q$$$. You need to output a single integer $$$p\cdot q^{-1} \mod (10^9+7)$$$.

2
2
5 8
1 2
1
4
1 2 3 4
1 2
2 3
2 4
2

Case 1: 8
Case 2: 666666674