Tousa Tree

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

inputFormat

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$

outputFormat

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

样例

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

4
10
43

</p>