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