Trees

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

最近壕lyonlys送给了sweetzero一棵神奇的树,这棵树是一个有根树,以1为根节点。

对于树上的每个非叶节点,对它的所有儿子按照编号字典序进行标号,即对其所有儿子节点按照编号大小排序后,最小编号的为其1节点,编号第k小的为其k节点。每当一个点的值增加1时,将引起其儿子节点增加标号值,即第k儿子节点增加k的值,这是一个递归增加的过程,即儿子节点的变化会同时导致儿子的儿子节点值的变化,直到某个点为叶子节点才结束增长。 壕lyonlys有些时候心情大好,就给sweetzero派钱(~)。

他有3种操作:

1.给节点u增加c的值。

2.给sweetzero发节点u为根的子树的值之和 % 1000000007这么多的钱

3.给sweetzero发节点u的值 % 1000000007的钱。

sweetzero由于数学是音乐老师教的,不会数数。您可以告诉他对于每个2或者3操作,他能得到多少钱吗?

Input

多组数据,每组数据:

第一行两个数N,M,表示树的节点总数为N和总操作数为M(1 <= N,M <= 10^5)

第二到N行,每行两个数x,y(1 <= x,y <= N),表示树上的一条边。

接下来M行,每行是3种操作之一,即

1 u c 或者 2 u 或者 3 u (1 <= u <= N, 1 <= c <= 10^8)

Output

对于每个2或者3操作,输出一行,sweetzero得到多少钱。

Sample Input

4 4
1 2
2 3
3 4
1 1 2
1 1 3
2 2
3 4
4 4
1 2
2 3
2 4
1 1 2
1 2 3
2 2
3 4

Sample Output

15
5
20
10

Source

sweetzero

Manager

Information
Solved Number16
Submit Number77
Problem Tags
data structures
math
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel