On Changing Tree

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem

Initially every vertex value is zero. For an update on vertex $v$, each descendant at distance $i$ from $v$ receives an addition of $x-i\cdot k$. A query asks for the current value of one vertex modulo $10^9+7$.

Input

The first line contains $n$. The second line contains the parents $p_2,\ldots,p_n$; it is empty when $n=1$. The next line contains $q$. Each query is one of:

• 1 v x k: for every vertex $u$ in the subtree of $v$, add $x-(depth_u-depth_v)\cdot k$ to its value.
• 2 v: query the current value of vertex $v$.

Output

For each operation of type 2, print the value modulo $1000000007$.

Subtasks

Subtask 1 (20%)

• The tree size and number of operations are at most 20.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• The tree size and number of operations are at most 2000.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le3\cdot10^5$.
• $0\le x,k<10^9+7$.

Example

Input

1

9
2 1
1 1 581999284 308872843
1 1 974853058 641941689
1 1 471382685 727846723
2 1
1 1 290788170 687681328
2 1
1 1 780587910 592803148
2 1

Output

0
28235013
319023183
99611086

Explanation

With one vertex, every update changes only that vertex because all descendant distances are zero.