Standing, Genn watched the sunlight flicker on the calm ocean. His whole body hurt, but his mind was clearer than it had been in weeks. He waited a moment, certain that his thoughts would soon become filled with memories he’d rather forget. But none haunted him now. The ships were separating from the flotilla. Now, with the trouble averted, each unraveled its own bright sail and glided out farther over the sun-speckled sea.
\space \space “You said to me that this Archdruid Stormrage believes my people will be an important asset to the Alliance.”
\space \space “That I did.”
\space \space “Perhaps he is right, then…. Perhaps he is right.”
Genn has a tree with n vertices, rooted at vertex 1. As a master of data structure, he performs mm "access" operations to the tree in chronological order. For the ith operation, vertex xi will be "accessed": all edges on the route from vertex xi to the root will be painted color ci. Meanwhile, the color of all other edges that have exactly one common vertex with the route will be reset to 0.
The value of the tree is defined as the sum of color on all edges after all operations are performed.
Unfortunately, painting on trees is really a dangerous task, so each operation has only piprobability to be performed successfully, and for probability 1−pi the operation will be skipped and nothing will happen to the tree.
Genn wants to know the expected value of the tree modulo 109+7.
Formally, let M=109+7. It can be demonstrated that the answer can be presented as a irreducible fractionqp, where p and q are integers and q！≡0(modM). Output a single integer equal to p⋅q−1modM. In other words, output an integer xx such that 0≤x<Mandx⋅q≡p(modM).
The input consists of multiple test cases.
The first line contains an integer T(1≤T≤4) denoting the number of test cases.
For each test case, the first line contains two integers n and m(1≤n,m≤2×105), denoting the number of vertices and the number of operations.
The second line contains n-11 integers f2,f3...fn(1≤fi≤i−1), fi is the parent of vertex ii.
Following mm lines describe the operations. Each line contains three integers xi,ci,pi(1≤xi≤n,1≤ci,pi<109+7). Note that p_ipi ought to be a fraction∈[0,1] but is given in the special form described above.
2
5 3
1 1 3 3
2 1 500000004
4 2 500000004
5 3 500000004
10 10
1 2 2 3 2 5 4 8 2
10 8042252 94637128
1 561941603 324991490
3 752444595 585213411
5 210303898 641078478
6 693964040 699726787
9 882181410 70805620
7 950609757 940002046
4 478347490 231203984
8 152593189 752354400
2 557926271 296109563125000005
34778673