You are given a tree $T$ with $N$ nodes rooted at $1$. The $i^{th}$ node of the tree has been assigned value $A_i$. You are required to handle two types of queries:

• $\text{1 v x}:$ Update the value of node $\text{v}$ to $\text{x}$, that is $A_\text{v} = x$.
• $\text{2 v}:$ Consider the multiset of values of nodes present in the subtree of node $\text{v}$. Consider all non-empty subsets of this set. Alice and Bob play a game on each of these subsets (independently) alternating turns.
  • For each subset, Alice starts the game. In each turn, the current player must choose some element of the current subset and reduce it to some non-negative element. The player who cannot make a move loses. Note that it is necessary to reduce or decrease the element.
  • You need to find the number of subsets where Bob is guaranteed to win. The number of subsets can be very large, output it modulo $1000000007(10^9+7)$

Input format

• The first line contains an integer that denotes the number of nodes in tree $T$.
• The second line contains $N$ space-separated integers denoting the initial value on the nodes of the tree($A_i$)
• $(N - 1)$ lines follow. Each of these lines contains two space-separated integers $u$ and $v$ denoting that there is an edge between these two nodes.
• The next line contains an integer $Q$ denoting the number of queries.
• $Q$ lines follow. Each line is a query of the type $\text{1 v x}$ or $\text{2 v}$.

Output format

For each query of type $\text{2 v}$, print the number of non-empty subsets of the multiset of values present in a subtree of node $\text{v}$ when Bob wins.

Constraints

$1 \leq N \leq 5 \times 10^5 \\ 1 \leq A_i \leq 10^6 \\ 1 \leq u, v \leq N \\ \text{Given edges form a tree} \\ 1 \leq Q \leq 10^5 \\ 1 \leq x \leq 10^6$