Once again we return to Ajobshohor, the capital city and the heart of Ajobdesh. Ajobshohor’s road system can be represented as a tree. There are n tollbooths, connected with n - 1 roads. Each tollbooth has an x-factor associated with it. The government has issued a new regulation, where every person traveling via that tollbooth has to pay an amount which is determined by a formula of F(x). However, the government can reissue the x-factor associated with any tollbooth, and update it in a single day.
F (x) => F (x -1) * k + F (x - 3) *( k - 2)
F (1) => 1
F (2) => 2
F (3) => 5
John is a freshly graduate software engineer who is relocating to Ajobshohor for his new internship; where he will stay for a duration of q days. Since his company has a rather flexible working environment, John can sometimes work remotely from his home; but on regular days he has to travel from point u to v.
For each of the q days, he asks you to either find the total amount spent by John commuting via the tollbooths or update the x-factor of the tollbooth due to reissuance of the government.
So the two types of queries are:
- Type 1:
- 1 u v, print the total toll paid by John, going from point u to v.
- Type 2:
- 2 u x, update the x-factor of tollbooth u.
As the sum can be quite big, print the sum modulo 109+7.
Input
The first line contains three integers n, q and k ( 1 ≤ n, q ≤ 105, and 1 ≤ k ≤ 50). The second line contains n integers x1, x2, …, xn, where xi is the initial x-factor of the node i. Each of the next n - 1 lines contains two integers ui, vi, ( 1 ≤ ui, vi ≤ n ), meaning there is an edge between ui and vi. Each of the next q lines contains a query as described above.
Constraints
1 ≤ n, q ≤ 105
2 <= k <= 50
1 <= xi <= 1018
1 ≤ ui , vi ≤ n
Output
For each query of type 1, print the sum in a new line.
Samples
| Input | Output |
|---|---|
5 5 2 4 1 1 4 2 2 1 3 1 5 2 4 1 2 3 3 1 3 4 1 5 1 1 4 3 2 3 4 | 25 13 25 |
| Input | Output |
|---|---|
5 5 3 2 2 3 1 5 5 1 3 1 2 1 4 3 1 4 5 2 1 4 2 1 4 2 5 4 1 1 5 | 58 32 |
| Input | Output |
|---|---|
5 5 5 2 5 3 3 5 2 1 5 4 3 1 4 3 1 1 5 2 4 2 2 2 1 2 2 5 2 1 3 | 158 |
