It is exam season at UTS, and the air is thick with the excitement of students preparing for their valiant battles against French words and comparative essays. In such a charged atmosphere, all sorts of shocking education-related events are occurring throughout the building on a regular basis.

Now, one should know that the ~N~ ~(1 \le N \le 10^5)~ UTS students love to spread this juicy academic gossip. In fact, their dedication to the activity is so great that they have set up a tree-shaped network to facilitate its spread, with each student represented by a node in the network.

When a student announces some piece of news, it spreads throughout the gossip network. The ~i^\text{th}~ student has popularity ~P_i~, and any news that he/she passes on will have its interest value multiplied by ~P_i~. This means that student ~s~ starts some gossip with interest value ~v~, when student ~t~ hears it, it will have an interest value of ~v\cdot product(s, t)~, where ~product(s, t)~ is the product of the popularities of all students on the path from ~s~ to ~t~ (The popularity of student ~t~ is not included in the product).

In order to maintain absolute control over all students' social lives, Principal Evans likes to be able to track the status of the network at all times.

There are two types of queries:

1. 1 s v: Student ~s~ ~(1 \le s \le N)~ announces some news of interest value ~v~ ~(1 \le v \le 10^9)~.

2. 2 s: Find the sum of the interest values of all the news that student ~s~ ~(1 \le s \le N)~ heard, including news that originated with ~s~. Output this number modulo ~10^9+7~.

Input Specification

The first line contains ~N~ and ~Q~, the number of students and the number of queries.

The second line contains ~N~ integers ~p_1, p_2, \dots, p_N~, the popularities of the ~N~ students. ~(1 \le p_i \le 10^9)~

The next ~N-1~ lines contain two integers ~a, b~ ~(1 \le a, b \le N)~, indicating that there is an edge in the network between students ~a~ and ~b~. It is guaranteed that the input describes a valid tree.

Each of the next ~Q~ lines contains a valid query in the format specified above.

Output Specification

For each type 2 query, output the answer on a separate line.

Constraints

Subtask 1 [20%]

~1 \le N, Q \le 10^3~

Subtask 2 [30%]

~1 \le N, Q \le 10^5~

The network is a straight path, where student ~i~ is connected to students ~i-1~ and ~i+1~, for all ~2 \le i \le N-1~. (~1~ and ~N~ are the endpoints of the path)

Subtask 3 [50%]

~1 \le N, Q \le 10^5~

Sample Input 1

3 3
2 5 4
1 2
2 3
1 1 3
2 3
2 1

Sample Output 1

30
3

Explanation for Sample Output 1

A piece of news with interest value ~3~ originates at student ~1~. When he/she tells it to student ~2~, its interest gets multiplied by ~p_1 = 2~. When student ~2~ tells it to student 3, it gets multiplied by ~p_2 = 5~. Thus, student 3 hears news with interest value ~3\cdot 2\cdot 5 = 30~.

To student ~1~, the news has interest value ~3~, because it was never multiplied by anyone's popularity.