You are given a tree with nodes.
The tree's nodes are numbered through and its edges are numbered through .
Each edge is associated with a distance.
There are lightbulbs, numbered from to . For each lightbulb you are given an integer - the node number where the lightbulb is, and no two lightbulbs in the same node. Each lightbulb can either be ON or OFF. Each input case will contain the initial state.
You're starting from node , and need to turn off all lightbulbs. And we can guarantee that there is no lightbulb at the starting point , and there is no more than one lightbulb in one node.
You can repeat the following operation until all lightbulbs are OFF:
If you are currently located in node , you will randomly select a new node with equal probability from {v: , should have no lightbulb if has a lightbulb}. Then you will move to node by the shortest path and flip (ON OFF, OFF ON) the lightbulb in if node has lightbulb.
Your task is to compute the expected total distance to light down all lightbulbs.

The first line of the input gives the number of test case,  ().  test cases follow.
For each case, the first line contains three integers , , and  (; ; ) -- the number of nodes, the number of lightbulbs, and the start position.
The i-th line of the next  lines describes the i-th edge: three integers u, v, w (; ; ) denotes an edge between u and v with distance w.
The i-th line of the next  lines contains two integers  (; ) and  () -- the positions of the i-th lightbulb and the initial states of the i-th lightbulb, where 1 means ON and 0 mean OFF.

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is answer modulo . More specifically, if the answer can be formed as an irreducible fraction , then   will be .

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

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