SP26843 INS16F - Who is the Best?

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**).

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 $ _{1} $ , V $ _{2} $ , V $ _{3} $ , ...... 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

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