提示: 欢迎访问OurACM平台。
Problem 2277 Change

Accept: 171    Submit: 852
Time Limit: 2000 mSec    Memory Limit : 262144 KB

Problem Description

There is a rooted tree with n nodes, number from 1-n. Root’s number is 1.Each node has a value ai.

Initially all the node’s value is 0.

We have q operations. There are two kinds of operations.

1 v x k : a[v]+=x , a[v’]+=x-k (v’ is child of v) , a[v’’]+=x-2*k (v’’ is child of v’) and so on.

2 v : Output a[v] mod 1000000007(10^9 + 7).

Input

First line contains an integer T (1 ≤ T ≤ 3), represents there are T test cases.

In each test case:

The first line contains a number n.

The second line contains n-1 number, p2,p3,…,pn . pi is the father of i.

The third line contains a number q.

Next q lines, each line contains an operation. (“1 v x k” or “2 v”)

1 ≤ n ≤ 3*10^5

1 ≤ pi < i

1 ≤ q ≤ 3*10^5

1 ≤ v ≤ n; 0 ≤ x < 10^9 + 7; 0 ≤ k < 10^9 + 7

Output

For each operation 2, outputs the answer.

Sample Input

1 3 1 1 3 1 1 2 1 2 1 2 2

Sample Output

2 1

Source

第八届福建省大学生程序设计竞赛-重现赛(感谢承办方厦门理工学院)

Submit  Back  Status  Discuss