You are given a tree (undirected) with $N$ nodes. Each node has a value $A_{i}$ ($1 \leq i \leq N$) associated with it.

You can delete a subset (including none) of the edges from this tree such that the following conditions hold:

1. There are no odd-sized components in the resulting graph.
2. Define $X$ as the sum of XOR’s of each component. The value of $X$ should be maximum.

Find the value of $X$ modulo $10^{9}+7$.

Note: XOR of a component is defined as the XOR of the values associated with all the nodes in that component.

Input

• The first line contains an integer $N$ denoting the number of nodes in the tree.
• Next line contains $N$ space-separated integers $A_{i}$ denoting the value associated of each node, as given in the problem statement.
• Next $N-1$ lines contain two space-separated integers $u$ and $v$ denoting an edge between nodes $u$ and $v$.

Constraints

• $1 \leq N \leq 5*10^{5}$
• $0 \leq A_{i} \leq 10^{9}$
• $N$ is even.

Output

• Output the value of $X$ modulo $10^{9}+7$ as stated in the problem statement.