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

- 1 u v, print the total toll paid by John, going from point
- Type 2:
- 2 u x, update the
**x-factor**of tollbooth**u**.

- 2 u x, update the

As the sum can be quite big, print the sum modulo **109+7**.

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

For each query of type **1**, print the **sum** in a new line.

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 |