397_E. On Changing Tree_5235
You are given a rooted tree consisting of n vertices numbered from 1 to n. The root of the tree is a vertex number 1.

Initially all vertices contain number 0. Then come q queries, each query has one of the two types:

  * The format of the query: 1 v x k. In response to the query, you need to add to the number at vertex v number x; to the numbers at the descendants of vertex v at distance 1, add x - k; and so on, to the numbers written in the descendants of vertex v at distance i, you need to add x - (i·k). The distance between two vertices is the number of edges in the shortest path between these vertices. 
  * The format of the query: 2 v. In reply to the query you should print the number written in vertex v modulo 1000000007 (109 + 7). 



Process the queries given in the input.

Input

The first line contains integer n (1 ≤ n ≤ 3·105) — the number of vertices in the tree. The second line contains n - 1 integers p2, p3, ... pn (1 ≤ pi < i), where pi is the number of the vertex that is the parent of vertex i in the tree.

The third line contains integer q (1 ≤ q ≤ 3·105) — the number of queries. Next q lines contain the queries, one per line. The first number in the line is type. It represents the type of the query. If type = 1, then next follow space-separated integers v, x, k (1 ≤ v ≤ n; 0 ≤ x < 109 + 7; 0 ≤ k < 109 + 7). If type = 2, then next follows integer v (1 ≤ v ≤ n) — the vertex where you need to find the value of the number.

Output

For each query of the second type print on a single line the number written in the vertex from the query. Print the number modulo 1000000007 (109 + 7).

Examples

Input

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


Output

2
1

Note

You can read about a rooted tree here: http://en.wikipedia.org/wiki/Tree_(graph_theory).
import java.util.*;
import java.io.*;
public class On_Changing_Tree
{
    static int N , Q ;
    static long BIT [][] = new long [2][300010];
    static long MOD = 1000000007;
    static ArrayList<ArrayList<Integer>> adjList =  new ArrayList<ArrayList<Integer>>();
    static int start[] =new int [300010];
    static int finish[]=new int [300010];
    static int timer = 0 ;
    static int level[] =new int [300010];
    public static void main(String[]args)
    {
        InputReader1 sc = new InputReader1(System.in);
        N = sc.nextInt();
        for(int i=0;i<=300010;i++)adjList.add(new ArrayList<Integer>());
        for(int i=2;i<=N;i++)
        {
            int par = sc.nextInt();
            adjList.get(par).add(i);
        }
        dfs(1,0);
        Q = sc.nextInt();
        StringBuilder output = new StringBuilder();
        while(Q-->0)
        {
            int type = sc.nextInt();
            int v = sc.nextInt();
            if(type==1)
            {
                long x = sc.nextLong();
                long k = sc.nextLong();
                update(0,x+k*level[v],start[v]);
                update(0,-x-k*level[v],finish[v]+1);
                update(1,k,start[v]);
                update(1,-k,finish[v]+1);
            }
            else
            {
                long v1 = query(0,start[v]);
                long v2 =  mod(query(1,start[v])*level[v]);
                long ans = mod(v1-v2);
                output.append(ans).append("\n");
            }
        }
        System.out.println(output);
    }
    static long mod(long x)
    {
        x%=MOD;
        if(x<0)x+=MOD;
        return x;
    }
    static void update(int id , long val , int idx)
    {
        for(;idx<=N;idx+=idx&-idx)
            BIT[id][idx]=mod(BIT[id][idx]+val);
    }

    static long query(int id , int idx)
    {
        long sum = 0;
        for(;idx>0;idx-=idx&-idx)
        sum=mod(sum+BIT[id][idx]);
        return sum;       
    }

    static void dfs(int node , int lvl)
    {
        start[node] = ++timer;
        level[node] = lvl;
        for(int next: adjList.get(node))    
            dfs(next,lvl+1);
        finish[node] = timer;    
    }
}
class InputReader1 
{

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public InputReader1(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c & 15;
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long nextLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c & 15;
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String next() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public String nextLine() {
        int c = read();
        //while (c != '\n' && c != '\r' && c != '\t' && c != -1)
        //c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (c != '\n' && c != '\r' && c != '\t' && c != -1);
        return res.toString();
    }

    public static boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

}   