题目描述

给定一棵以 $1$ 为根的有根树，初始所有节点颜色为 $1$，每次将距离节点 $a$ 不超过 $l$ 的 $a$ 的子节点染成 $c$，或询问点 $a$ 的颜色。

输入格式

第一行一个数 $T$，表示数据组数。

接下来每组数据的第一行三个数 $n,c,q$ 表示结点个数，颜色数和操作数。

接下来一行 $n-1$ 个数描述 $2\cdots n$ 的父节点。

接下来 $q$ 行每行三个数 $a,l,c$。

若 $c$ 为 $0$，表示询问 $a$ 的颜色，否则将距离 $a$ 不超过 $l$ 的 $a$ 的子节点染成 $c$。

输出格式

设当前是第 $i$ 个操作，$y_i$ 为本次事件之后的答案，令 $z_i=i\times y_i$，请输出 $z_1+z_2+...+z_q$ 模 $10^9+7$ 之后的值。

1
4 3 7
1 2 2
3 0 0
2 1 3
3 0 0
1 0 2
2 0 0
4 1 1
4 0 0

32

数据规模与约定

对于 $100\%$ 的数据，$1\leq T\leq 6$，$1\leq n,m,c\leq 10^5$，$1\leq a,l,c\leq n$。