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\)