INS16F - Who is the Best?

no tags 

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 V1, V2, V3, ...... VN where Vi indicates the Varys_Value of ith 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 ≤ Vi ≤ 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


Added by:Adarsh kumar
Date:2016-04-10
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:INSOMNIA 2016