威廉种了一棵有根树，珂朵莉非常喜欢这棵树，所以威廉决定把这棵树叫做珂朵莉树。

    威廉每天都细心修饰这棵有根树，树上每一个结点都有一个精美值，他有两种操作：

    操作一：他会将以 为根结点的子树的所有结点的精美值都设为 。

    操作二：他会问你以 为根结点的子树的所有结点的精美值的 次方之和。

    树是一张无环连通图，有根树的根节点入度为 0 。

输入描述:

第一行四个整数  ，分别表示有根树结点个数（根结点为  ）操作次数，随机数种子，取值范围。

后续输入将由选手使用给定的随机函数手动生成（提示处有伪代码）

接下来一行  个数  表示各个结点的精美值。

接下来  行，每行两个整数  表示结点  之间有一条树边。

接下来  行，每行三个整数  代表一次操作， 代表操作一， 代表操作二，  的意义如题目描述。

输出描述:

对于每一次操作二，输出一个整数。由于答案可能太大，所以你需要将其对  取模。

5 5 1 5

4149
1

备注:

提示：

def rnd():   //随机函数
    ret = seed
    seed = (seed * 7 + 13) mod 1000000007
    return ret;

for int i = 1 to n:  // 节点赋值
    a[i] = (rnd() mod vmax) + 1

for int i = 2 to n:  //建树
    u = i
    v = (rnd() mod (i - 1)) + 1

for int i = 1 to m:  // 操作
    op = (rnd() mod 2) + 1
    u = (rnd() mod n) + 1
    x = (rnd() mod vmax) + 1

样例1解释 ：
通过随机数种子seed产生的后续输入为
2 1 4 5 2
2 1
3 2
4 3
5 2
1 4 3
1 4 5
2 3 5
1 3 1
2 4 4

可得答案为 ：
4149
1