1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 #define maxn 100005
  6 typedef long long LL;
  7 const int mo=1000000007;
  8 int pre[maxn],last[maxn],other[maxn];
  9 int st[maxn],en[maxn],dep[maxn];
 10 int n,m,q,l,T,tot,rt,cmp_d,now[2];
 11 LL ans;
 12 struct KD_tree
 13 {
 14     int ls,rs;
 15     int d[2],mn[2],mx[2];
 16     int col,lazy;
 17 }t[maxn];
 18  
 19 inline int read(void)
 20 {
 21     int x=0;
 22     char ch=getchar();
 23     while (ch>‘9‘||ch<‘0‘) ch=getchar();
 24     while (ch>=‘0‘&&ch<=‘9‘)
 25     {
 26         x=x*10+ch-‘0‘;
 27         ch=getchar();
 28     }
 29     return x;
 30 }
 31  
 32 void connect(int x,int y)
 33 {
 34     l++;
 35     pre[l]=last[x];
 36     last[x]=l;
 37     other[l]=y;
 38 }
 39  
 40 void dfs(int u)
 41 {
 42     st[u]=++tot;
 43     for (int p=last[u];p;p=pre[p])
 44     {
 45         int v=other[p];
 46         dep[v]=dep[u]+1;
 47         dfs(v);
 48     }
 49     en[u]=tot;
 50 }
 51  
 52 inline bool cmp(KD_tree a,KD_tree b)
 53 {
 54     int x=a.d[cmp_d],y=b.d[cmp_d];
 55     return x<y||(x==y&&a.d[!cmp_d]<b.d[!cmp_d]);
 56 }
 57  
 58 void KD_update(int x)
 59 {
 60     int ls=t[x].ls;
 61     int rs=t[x].rs;
 62     if (ls) 
 63     {
 64         t[x].mn[0]=min(t[x].mn[0],t[ls].mn[0]);
 65         t[x].mx[0]=max(t[x].mx[0],t[ls].mx[0]);
 66         t[x].mn[1]=min(t[x].mn[1],t[ls].mn[1]);
 67         t[x].mx[1]=max(t[x].mx[1],t[ls].mx[1]);
 68     }
 69     if (rs)
 70     {
 71         t[x].mn[0]=min(t[x].mn[0],t[rs].mn[0]);
 72         t[x].mx[0]=max(t[x].mx[0],t[rs].mx[0]);
 73         t[x].mn[1]=min(t[x].mn[1],t[rs].mn[1]);
 74         t[x].mx[1]=max(t[x].mx[1],t[rs].mx[1]);
 75     }
 76 }
 77  
 78 int KD_build(int l,int r,int D)
 79 {
 80     int mid=(l+r)>>1;
 81     cmp_d=D;
 82     nth_element(t+l,t+mid,t+r+1,cmp);
 83     t[mid].mn[0]=t[mid].mx[0]=t[mid].d[0];
 84     t[mid].mn[1]=t[mid].mx[1]=t[mid].d[1];
 85     t[mid].col=1;t[mid].lazy=0;
 86     t[mid].ls=t[mid].rs=0;
 87     if (l<mid) t[mid].ls=KD_build(l,mid-1,D^1);
 88     if (r>mid) t[mid].rs=KD_build(mid+1,r,D^1);
 89     KD_update(mid);
 90     return mid;
 91 }
 92  
 93 inline void push_down(int x)
 94 {
 95     if (!t[x].lazy) return;
 96     int ls=t[x].ls,rs=t[x].rs;
 97     if (ls) t[ls].col=t[ls].lazy=t[x].lazy;
 98     if (rs) t[rs].col=t[rs].lazy=t[x].lazy;
 99     t[x].lazy=0;
100 }
101  
102 int KD_ask(int x,int D)
103 {
104     if (t[x].d[0]==now[0]&&t[x].d[1]==now[1]) return t[x].col;
105     push_down(x);
106     if (now[D]<t[x].d[D]||(now[D]==t[x].d[D]&&now[!D]<t[x].d[!D]))
107         return KD_ask(t[x].ls,D^1);
108     else
109         return KD_ask(t[x].rs,D^1);
110 }
111  
112 inline pair<bool,bool> in(int x,int x1,int y1,int x2,int y2)
113 {
114     bool p1= t[x].mn[0]>=x1&&t[x].mx[0]<=x2&&t[x].mn[1]>=y1&&t[x].mx[1]<=y2;
115     bool p2= t[x].d[0]>=x1&&t[x].d[0]<=x2&&t[x].d[1]>=y1&&t[x].d[1]<=y2;
116     return make_pair(p1,p2);
117 }
118  
119 inline bool out(int x,int x1,int y1,int x2,int y2)
120 {
121     return t[x].mx[0]<x1||t[x].mn[0]>x2||t[x].mx[1]<y1||t[x].mn[1]>y2;
122 }
123  
124 void KD_add(int x,int x1,int y1,int x2,int y2,int c)
125 {
126     if (!x) return;
127     push_down(x);
128     if (in(x,x1,y1,x2,y2).first) 
129     {
130         t[x].col=t[x].lazy=c;
131         return;
132     }
133     if (out(x,x1,y1,x2,y2)) return;
134     if (in(x,x1,y1,x2,y2).second) t[x].col=c;
135     KD_add(t[x].ls,x1,y1,x2,y2,c);
136     KD_add(t[x].rs,x1,y1,x2,y2,c);
137 }
138  
139 int main()
140 {
141     T=read();
142     while (T--) 
143     {
144         memset(last,0,sizeof last);l=tot=0;
145         n=read();m=read();q=read();
146         for (int i=2;i<=n;i++)
147         {
148             int fa=read();
149             connect(fa,i);
150         }
151         dfs(1);
152         for (int i=1;i<=n;i++) t[i].d[0]=st[i],t[i].d[1]=dep[i];
153         rt=KD_build(1,n,0);
154         ans=0;
155         for (int i=1;i<=q;i++) 
156         {
157             int x=read(),y=read(),c=read();
158             if (c==0) 
159             {
160                 now[0]=st[x];now[1]=dep[x];
161                 y=KD_ask(rt,0);
162                 ans=(ans+(LL)y*i)%mo;
163             }
164             else
165             {
166                 int x1=st[x],y1=dep[x];
167                 int x2=en[x],y2=dep[x]+y;
168                 KD_add(rt,x1,y1,x2,y2,c);
169             }
170         }
171         printf("%lld\n",ans);
172     }
173     return 0;
174 }