Genn 拥有一棵有 $n$ 个顶点的树，根节点为 1。作为一名数据结构大师，他按时间顺序对这棵树执行了 $m$ 次“访问”操作。对于第 $i$ 次操作，顶点 $x_i$ 将被“访问”：从顶点 $x_i$ 到根节点的路径上的所有边都将被涂上颜色 $c_i$。同时，所有与该路径恰好有一个公共顶点的其他边的颜色将被重置为 0。

树的权值定义为所有操作完成后所有边上的颜色之和。

不幸的是，在树上涂色是一项非常危险的任务，因此每次操作只有 $p_i$ 的概率成功执行，而有 $1 - p_i$ 的概率该操作会被跳过，树不会发生任何变化。

Genn 想知道树的期望权值，结果对 $10^9 + 7$ 取模。

形式化地，令 $M = 10^9 + 7$。可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod M$。输出一个整数，等于 $p \cdot q^{-1} \pmod M$。

换句话说，输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod M$。

输入格式

输入包含多个测试用例。

第一行包含一个整数 $T(1 \le T \le 4)$，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 2 \times 10^5$)，分别表示顶点数和操作数。

第二行包含 $n - 1$ 个整数 $f_2, f_3, \dots, f_n$ ($1 \le f_i \le i - 1$)，$f_i$ 是顶点 $i$ 的父节点。

接下来的 $m$ 行描述操作。每行包含三个整数 $x_i, c_i, p_i$ ($1 \le x_i \le n, 1 \le c_i, p_i < 10^9 + 7$)。注意，$p_i$ 本应是一个分数 $\in [0, 1]$，但以题目描述的特殊形式给出。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示答案。

样例

输入 1

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

输出 1

125000005
34778673