熊猫先生和他的朋友们被困在一个有 $N$ 个房间的迷宫中。房间由双向门连接，且该迷宫恰好是一棵树（即迷宫中没有环）。每个房间都有一个分配的数值 $v_i$。

经过在迷宫内的一些探索，熊猫先生发现一个房间最多只能进入两次。在进入一个房间两次后，该房间的致命陷阱就会被激活，此后进入该房间将不再安全。注意，熊猫先生开始探索时所在的房间在初始时被视为已进入过一次。

熊猫先生和他的朋友们最初位于房间 $S$。由于他们不知道如何逃离迷宫，他们决定随机移动。在每一步中，他们会在所有仍然安全的相邻房间中等概率地选择下一个房间。他们不断地从一个房间移动到另一个房间，直到被困在某个房间，即从该房间出发没有安全的下一个房间可供选择。

作为一名算法极客，熊猫先生想知道最后一个房间的期望值是多少。

输入格式

输入的第一行包含测试用例的数量 $T$ ($1 \le T \le 10$)。接下来是 $T$ 个测试用例。

对于每个测试用例，第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示房间的数量。 下一行包含 $N$ 个整数 $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 1000$)，表示每个房间分配的数值。 接下来的 $N-1$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le N$)，描述迷宫的边。 最后一行包含一个整数 $S$ ($1 \le S \le N$)，表示初始房间编号。

输出格式

对于每个测试用例，输出一行 “Case x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是最后一个房间的期望值。期望值 $y$ 可以写成最简分数 $p/q$。你需要输出一个整数 $p \cdot q^{-1} \pmod{10^9 + 7}$。

样例

输入 1

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

输出 1

Case 1: 8
Case 2: 666666674