Description

曾经有个星系其中有n个星球，有一颗恒星叫死星，其他行星以它为根构成一颗树。

其中死星的编号是1，其他行星编号为2～n。

每个星球有个发展程度为vi，一开始因为每个星球都至少有文明存在，所以初始的时候vi=1。

定义两个星球之间星际穿越的代价为路径上的发展程度之和，因为发展程度越高需要的过路费越高。

然后会有m次大事件发生，总共有两种类型。

技术爆炸：1 p x表示p号点的发展程度增加x。

技术交流：2 p 表示询问p子树内所有点对的星际穿越的代价之和(mod 10^9+7)。

（点对的两点可以相同）

请输出每次技术交流的结果

Format

Input

第一行两个正整数n,m。

接下来n-1行，每行两个数u,v表示u,v两颗行星在树上相连。

接下来m行，每行第一个数opt表示事件的类型。 然后根据opt=1,2有2,1个正整数。

pi ≤ n 且 vi < 10^9 + 7

N,M<=2*10^5

Output

对于每个技术交流的事件输出一行正整数表示答案。

Samples

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

1
33
4
10