Problem Description

Xiao X has given you a tree with $n$ nodes, each having a node weight.

You need to calculate the value of the following expression modulo $786433$:

$\sum_{1\leq u\leq v\leq n}f(u,v)^{f(u,v)}$

where $f(u,v)$ represents the bitwise AND of the weights of all nodes on the shortest path from $u$ to $v$.

Hint: For convenience in your calculations, we consider $0^0=0$. Additionally, $786433$ is a prime number and an uncommon NTT modulus, with a primitive root of $10$. If you are unfamiliar with NTT or primitive roots, you can ignore this hint.

Input Format

The first line contains a positive integer $n$, representing the number of nodes in the tree.

The second line contains $n$ positive integers $a_{1\dots n}$, where $a_i$ represents the weight of the node with the number $i$.

The next $n-1$ lines each contain two positive integers $u$ and $v$, indicating that there is an edge between the node numbered $u$ and the node numbered $v$.

Data Range:

• $2 \le n \le 2 \times 10^5$.
• For all $i$ such that $1 \le i \le n$, $1 \le a_i < 2^{30}$.
• $1 \le u,v \le n, u \ne v$.
• Let $d$ be the number of leaf nodes (nodes with degree 1) in the tree. The data guarantees that $4\le n \cdot d \le 3 \times 10 ^ 6$.

Output Format

A single integer representing the answer modulo $786433$.

Sample Input and Output

Sample Input #1

10
15 50 89 9 38 73 38 23 6 52
2 1
3 2
4 2
5 3
6 3
7 5
8 7
9 1
10 7

Sample Output #1

54184

Sample Input #2

20
17 56 72 12 16 43 33 8 28 90 21 12 7 43 55 95 25 65 63 77
2 1
3 2
4 1
5 3
6 5
7 1
8 7
9 7
10 3
11 5
12 7
13 5
14 7
15 11
16 6
17 3
18 15
19 15
20 13

Sample Output #2

503636

见题面 Input 部分

见题面 Output 部分