You are given a tree $G$ consisting of $N$ nodes. The $i^{th}$($1 \leq i \leq N$) node of the tree has been assigned a binary value $A_i$, that is $A_i = 0/1$. You are also given $Q$ queries.

In each query, you are given 2 nodes $u$ and $v$. Initialize an empty string. Now, consider the simple path between these 2 nodes(from $u$ to $v$) and append the binary values obtained on this path to the string. Your task is to find the decimal representation of this binary string. Note that the bit at $v$ corresponds to LSB.

Since the output can be very large, you need to calculate the decimal representation modulo $1000000007$ $(10^9+7)$

You are given $T$ test cases.

Warning: Use FAST I/O Methods. 

Input format

• The first line contains a single integer $T$ denoting number of test cases.
• For each test case:
  • The first line contains an integer $N$ denoting the number of nodes in tree.
  • Second line contains $N$ space separated integers denoting the values of the nodes.
  • Next $N-1$ lines follow. For each line:
    • Two space-separated integers $u$ and $v$ denoting the nodes of the tree. This means there is an edge between node $u$ and $v$.
  • Next line contains $Q$ denoting the number of queries.
  • $Q$ lines follow. Each line contains 2 space separated integers $u$ and $v$.

Output format

For each test case(in a separate line), output(in a separate line) $Q$ space separated integers where the $i^{th}$ integer denotes the decimal representation of the binary string obtained on the simple path between the two vertices in the $i^{th}$ query. Don't forget to take modulo $1000000007$ $(10^9+7)$

Constraints

$1 \le T \le 1000 \\ 1 \leq N, Q \leq 5 \times 10^5 \\ 0 \leq A_i \leq 1 \\ 1 \le u, v \le N \\ \text{It is guaranteed that given edges form a tree} \\ \text{Sum of N over all test cases does not exceed } 5 \times 10^5 \\ \text{Sum of Q over all test cases does not exceed } 5 \times 10^5$