INS14L - Rooted Trees

no tags 

Digo is given a rooted tree where nodes are numbered from 1 to N (1 is the root node) and asked some queries on it.

There are two types of queries:

  1. Given node number U, two integers X, K which means add X to the given node, X+K to its children, X+2*K to children of its children and so on.
  2. Given a node number U print the sum of nodes in the subtree rooted at U (including node U).

Since the answer can be too long, print the answer 10^9 + 7

Initially each node contains zero.

Input

First line contains a single integer N denoting the number of nodes in the tree.

Next N-1 lines denotes the parent node of nodes 2 to N. (1 is the root node it has no parent.)

Next line contains M (Number of queries.)

In each of the next M lines first integer is T which means the type of the query. If T is 1, it is followed by three integers U, X, K as explained in the question. If T is 2, it is followed by a single integer U.

Output

For each query of type 2, output a single line containing the required answer.

Constraints

1 <= N <= 100000

1 <= M <= 100000

1 <= X, K <=1000000000

Sample

Input
7
1
1
2
2
3
3
5
1 1 1 2
2 1
2 3
1 3 2 1
2 3

Output
27
13
21


Added by:Surya Kiran
Date:2014-03-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Insomnia 2014