CSG-CPC
Online Judge

1217 : ytree

         Time Limit: 2 Sec     Memory Limit: 512 Mb     Submitted: 15     Solved: 7    

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