SIMPLEPATH - Simple Path

You will be given a weighted rooted tree, where root is node 1. For each subtree of that tree, you will have to compute the summation of lengths of all possible simple paths present in that subtree. Eventually you need to print the summation of those values modulo 1000000007.

Image of the tree in the first sample is given below.

Image of the tree in the first sample is given below.

Input

First line of input will contain an integer T (1 <= T <= 10) denoting the number of test cases. Each test case will begin with an integer N (1 <= N <= 100000), indicating number of nodes. The following N-1 lines will have three integers each, U (1 <= U <= N), V (1 <= V <= N), W (1 <= W <= 1000000000), which denotes that there is an edge in the tree from node U to node V having W weight.

Input File is large. Use fast I/O methods.

Output

For each test case, print the case number then print the answer to the problem modulo 1000000007 in separate lines.

Example

Input:
2
7
1 2 3
1 3 2
2 4 1
2 5 4
3 6 6
3 7 8
6
1 2 3
1 3 2
1 4 4
3 5 7
3 6 1

Output:
Case 1: 212
Case 2: 109

Explanation of Sample

Explanation of the 1st sample: Summation of lengths of all possible sample paths for each subtree is given below:

  • 1: 174
  • 2: 10
  • 3: 28
  • 4: 0
  • 5: 0
  • 6: 0
  • 7: 0

Explanation of the 2nd sample: Summation of lengths of all possible sample paths for each subtree is given below:

  • 1: 93
  • 2: 0
  • 3: 16
  • 4: 0
  • 5: 0
  • 6: 0

Added by:Sourav Sen Tonmoy
Date:2017-04-07
Time limit:0.5s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem. Used in NHSPC 2017 Final Round. More about NHSPC: nhspc.org

hide comments
2020-09-08 11:54:08 suhash
Note: The constraints on W are incorrect (1 <= W <= 1e9). Got several WA assuming that it fits in a signed 32 bit integer. Changing to use a signed 64 bit integer worked.
2018-12-29 17:28:53
To submit, follow the link -> https://www.spoj.com/submit/SIMPLEPATH/
2018-08-09 00:18:24
Submission link, please.
2017-07-06 19:24:14
Submission link, please.
2017-06-06 08:05:55 Shubham Jadhav
where is the submission link??
2017-05-24 05:24:58
why can't i submit the solution?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.