Problem

You were asked by your friend Tousa the day before yesterday. He wants to decorate a tree with an arithmetic progression and use it for a birthday party, but the tree is too big to be used alone. Therefore, he wants you, an excellent programmer, to write a program that efficiently decorates a tree with arithmetic progressions. You and Tousa are old friends. You decide to accept Tousa's request.

You will be given a tree of $ N $ nodes to decorate. The nodes of the tree are numbered from $ 0 $ to $ N-1 $. Initially, all tree nodes score $ 0 $. The program must respond to the following two queries:

• $ 0 $. Finds the sum of the points written on the nodes of the specified section of the tree.
• $ 1 $. Adds an arithmetic progression to the nodes in the specified section of the tree.

Beautifully decorate the trees to celebrate Tousa's birthday.

Constraints

The input satisfies the following conditions.

• All inputs are integers
• $1 \ le N, Q \ le 10 ^ 5$
• $0 \ le A, B, S, T \ le N-1$
• $0 \ le K, M \ le 10 ^ 5$

Input

The input is given in the following format.

$ N $ $ Q $
$ A_0 $ $ B_0 $
$ A_1 $ $ B_1 $
::
$ A_ {N-2} $ $ B_ {N-2} $
$ COM_0 $
$ COM_1 $
::
$ COM_ {Q-1} $

The number of nodes in the tree $ N $ and the number of queries $ Q $ are given in the $ 1 $ row. Then the $ N-1 $ line is given information about the edges of the tree. $ A_i $, $ B_i $ indicate that there is an edge directly between the nodes $ A_i $ and $ B_i $. After that, $ Q $ instructions $ COM_j $ are given.

The format of $ COM_j $ is as follows.

$ 0 $ $ S $ $ T $

$ S $ and $ T $ are vertex numbers. The interval is specified by two nodes. This is the interval in which the shortest route from $ S $ to $ T $ is specified. Report the sum of the points written on the nodes included in the interval. However, $ S $ and $ T $ are also included in the interval. The answer can be very large, so print out the remainder divided by $ 10 ^ 9 + 7 $.

$ 1 $ $ S $ $ T $ $ K $ $ M $

As above, add points to the nodes included in the interval specified by $ S $ and $ T $. The points to be added are calculated as follows, assuming that the shortest distance from $ S $ is $ L $.

$K + L {\ times} M$

Output

When querying $ 0 $, the sum of the points written in the nodes included in the specified interval is output in one line.

Examples

Input

3 3
0 2
1 2
1 1 0 0 1
0 0 2
0 0 1

Output

3
3

Input

5 6
1 0
2 0
3 2
4 1
1 1 4 0 4
0 4 1
1 3 0 7 3
0 2 2
1 4 1 8 0
0 4 2

Output

4
10
43

见题面

见题面