Ajob Commute II

CLown1331 Ada Lovelace National Gir...
Limits 2s, 256 MB

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

InputOutput
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
InputOutput
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
InputOutput
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

Submit

Login to submit.

Statistics

100% Solution Ratio
mahdi.hasnatEarliest, Dec '19
nahid08Fastest, 0.5s
NJRafiLightest, 11 MB
mumith_fahim99Shortest, 4091B
Toph uses cookies. By continuing you agree to our Cookie Policy.