There is a tree with n(n<=100000) nodes.The root is a node with number 1.
The i-th node has a value val[i](0<val[i]<1000000000+7).
Define the value of a connected component as the product of each node's value.
White Cloud has 3 types of operation.
The first operation is to change a node's value.
The second operation is to change a node's father.
The third operation is to give 2 integers b and c, denoting querying the sum of value of all connected components which contains node b of size c.
输入描述:
The first line of input contains 2 integers n and m(n,m<=100000).
In the next line, there are n integers, denoting val[1..n].
In the next line, there are n-1 integers, denoting the father from the 2-th node to the n-th node.
In the next m lines, the first number a is the type of operation.
if a=0, the next 2 integers b and c(1 <= b <= n,0<c<1e9+7) denote changing the value of b to c.
if a=1, the next 2 integers b and c(1 <= b,c <= n，c is not in the subtree of b) denote changing the father of b to c.
if a=2, the next 2 integers b and c(1 <= b <= n,0<c <= 10) denote querying the sum of value of all connected components which contains node b of size c.
输出描述:
For each operation, if a=2, print a single line containing the answer modulo 1000000000+7.
示例1
输入
复制
3 3
1 2 3
1 1
2 1 2
2 1 3
2 2 3