Gilneas

$\space \space$*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 $m$ "access" operations to the tree in chronological order. For the $i^{th}$ operation, vertex $x_i$ will be "accessed": all edges on the **route** from vertex $x_i$ to the root will be painted color $c_i$. 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 $p_i$ probability to be performed successfully, and for probability $1-p_i$ the operation will be skipped and nothing will happen to the tree.

Genn wants to know the expected value of the tree **modulo $10^9+7$**.

Formally, let $M=10^9+7$. It can be demonstrated that the answer can be presented as a irreducible fraction $\dfrac{p}{q}$, where $p$ and $q$ are integers and $q\not\equiv 0 \pmod M$. Output a single integer equal to $p\cdot q^{-1} \bmod M$. In other words, output an integer $x$ such that $0\leq x < M$ and $x\cdot q \equiv p \pmod M$.

The input consists of multiple test cases.

The first line contains an integer $T (1\leq T \leq 4)$ denoting the number of test cases.

For each test case, the first line contains two integers $n$ and $m$ $(1\leq n,m \leq 2\times 10^5)$, denoting the number of vertices and the number of operations.

The second line contains $n-1$ integers $f_2,f_3...f_n(1\leq f_i\leq i-1)$, $f_i$ is the parent of vertex $i$.

Following $m$ lines describe the operations. Each line contains three integers $x_i,c_i,p_i (1\leq x_i\leq n, 1\leq c_i,p_i<10^9+7)$. Note that $p_i$ ought to be a fraction $\in [0,1]$ but is given in the special form described above.

For each test case, output one line containing one integer indicating the answer.

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 296109563

125000005
34778673

2022“杭电杯”中国大学生算法设计超级联赛（8）