Description

X gives you a tree with $n$ nodes, and each node has a weight.

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

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

Here, $f(u,v)$ is the value obtained by taking the bitwise AND of the weights of all nodes on the shortest path from $u$ to $v$.

Hint: To make calculation easier, we define $0^0=0$. Also, $786433$ is a prime number and an uncommon NTT modulus, whose primitive root is $10$. If you do not know what NTT is or what a primitive root is, you can ignore this hint.

Input Format

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

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

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

Constraints:

• $2 \le n \le 2 \times 10^5$.
• For all $i$ satisfying $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 leaves in the tree (nodes with degree $1$). The testdata guarantees that $4\le n \cdot d \le 3 \times 10 ^ 6$.

Output Format

Output one integer on one line, the answer modulo $786433$.

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

54184

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

503636

Hint

Translated by ChatGPT 5