1217 : ytree

Description

小Y很羡慕设计出自己数据结构的人，于是小Y也尝试设计一种新的树型结构想要支持以下操作:

• \(1\) \(v\) \(x\) \(k\)，设 \(u\) 是以 \(v\) 号点为根的子树中的一个点(\(u\) 可以等于\(v\))，若 \(u\) 与 \(v\) 的深度差为 \(d\)，则给 \(u\) 号点加上 \((x+k*d)*(-1)^{d}\)
• \(2\) \(v\)，询问\(v\) 号点的权值 \(mod (1e9+7)\)之后的值， (规定1 号节点为根)
• \(3\) \(v\)，将之前操作在以\(v\)为根的子树（包括\(v\)）的操作\(1\)都撤销

Input

第一行包含两个正整数 \(N\) 和\(M\)，\(N\) 为树上的点数，\(M\) 操作的数量。

第\(2\)~\(N\) 行，每行一个正整数，第\(i\)行的正整数是\(i\)号节点的父亲。

再接下来 \(M\) 行，格式为”\(1\) \(v\) \(x\) \(k\)“，”\(2\) \(v\)“或”\(3\) \(v\)“，含义如题。

对于 \(100\%\) 的数据， \(1 \leq n \leq 2*10^5\), \(1 \leq m \leq 10^5\), \(1 \leq |x|, |k| \leq 10^3\)。

Output

对于每个\(2\) 操作输出一行，为 \(v\)号点的权值\(mod (1e9+7)\)之后的值，负数取模要化为正数 （详见样例 ）

Sample

5 11
1
1
3
3
1 1 0 2
2 1
2 2
3 3
2 4
3 1
1 3 1 3
2 3
2 4
3 1
2 1

0
1000000005
4
1
1000000003
0

Hint

Source