给定一棵包含 $N$ 个节点的树。树的节点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。每条边都有一个距离。

共有 $M$ 个灯泡，编号从 $1$ 到 $M$。对于每个灯泡 $i$，给定一个整数 $p_i$，表示灯泡所在的节点编号，且没有两个灯泡位于同一个节点。每个灯泡的状态可以是开（ON）或关（OFF）。每个输入用例都包含灯泡的初始状态。

你从节点 $S$ 出发，需要关掉所有的灯泡。保证起始节点 $S$ 上没有灯泡，且每个节点上最多只有一个灯泡。

你可以重复执行以下操作，直到所有灯泡都处于关闭状态：如果你当前位于节点 $u$，你将从集合 $\{v : v \neq u, v \text{ 处不应有灯泡（若 } u \text{ 处有灯泡）}\}$ 中等概率随机选择一个新节点 $v$。然后，你将沿最短路径移动到节点 $v$，如果节点 $v$ 上有灯泡，则翻转该灯泡的状态（ON $\to$ OFF，OFF $\to$ ON）。

你的任务是计算关掉所有灯泡所需的总距离的期望值。

输入格式

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

对于每个测试用例，第一行包含三个整数 $N, M, S$ ($1 \le N \le 100,000; 1 \le M < N; 1 \le S \le N$)，分别表示节点数、灯泡数和起始位置。

接下来的 $N-1$ 行中，第 $i$ 行描述第 $i$ 条边：三个整数 $u, v, w$ ($1 \le u, v \le N; u \neq v; 1 \le w \le 100,000$)，表示节点 $u$ 和 $v$ 之间有一条距离为 $w$ 的边。

接下来的 $M$ 行中，第 $i$ 行包含两个整数 $p_i$ ($1 \le p_i \le N; p_i \neq S$) 和 $s_i$ ($0 \le s_i \le 1$)，表示第 $i$ 个灯泡的位置及其初始状态，其中 $1$ 表示 ON，$0$ 表示 OFF。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是答案对 $(10^9 + 7)$ 取模的结果。更具体地说，如果答案可以表示为不可约分数 $\frac{A}{B}$，则 $y$ 为 $(A \cdot B^{-1}) \pmod{10^9 + 7}$。

样例

输入 1

3
3 2 1
1 2 1
1 3 1
2 1
3 1
3 1 1
1 2 1
1 3 1
2 1
3 1 3
1 2 1
1 3 1
2 1

输出 1

Case #1: 7
Case #2: 333333338
Case #3: 666666674