Baratheon is one of the oldest houses in the Land of Seven Kingdoms. There have been many kings and their many heirs. The hierarchy is represented as a tree where each character is a node with initial value as the Varys_Value given by Lord Varys. You are the analyser appointed to the current King to give insights about a character.

There are Q commands given by the King which can be any of the following type:
1. Multiply the Varys_Value of all the characters in path from u to v by a given number P.
2. For a given character X, find the number of ordered pairs (i,j) such that LCM(i,j) is equal to current value at node X. (Insight)

For commands of second type, print the number of such pairs (modulo 1000000007).

Input

First line contains 2 space separated integers N and Q indicating the number of total characters and number of queries you need to answer.

In the next N-1 lines, each line contains 2 integers u, v which indicates a relationship between character u and character v.

Next line contains N space separated integer V₁, V₂, V₃, ...... V_N where V_i indicates the Varys_Value of i^th character.

Following Q lines contains the queries to be answered.
Types of Queries:

1 u v P - Query of first type

2 X - Query of second type

Output

For each query of second type, print the answer to the query in a new line.

Constraints

1 ≤ N ≤ 100000
1 ≤ Q ≤ 100000
1 ≤ u, v ≤ N
1 ≤ P ≤ 100
1 ≤ V_i ≤ 100000

Example

Sample Input:
6 6 
1 2
4 6
1 3
5 1
4 5
7 8 4 8 1 2
1 2 1 14
2 4
1 6 5 10
2 5
1 6 4 10
2 1

Sample Output:
7
9
15