Tree Path Bitwise-And Exponentiation

You are given a tree consisting of n nodes, where each node has an associated weight. For any two nodes u and v, define \(f(u,v)\) as the bitwise AND of all node weights along the unique shortest path from \(u\) to \(v\) in the tree.

Your task is to compute the following sum modulo \(786433\):

[ S = \sum_{1 \le u \le v \le n} f(u,v)^{f(u,v)} \pmod{786433}, ]

Note:

• For this problem, we define \(0^0 = 0\).
• The number \(786433\) is prime and is commonly used as an NTT modulus (its primitive root is \(10\)). You may ignore details regarding NTT if they are unfamiliar to you.

inputFormat

The first line contains a single integer \(n\) representing the number of nodes in the tree.

The second line contains \(n\) integers. The \(i\)-th integer indicates the weight of node \(i\).

Each of the following \(n-1\) lines contains two integers \(u\) and \(v\) signifying an undirected edge between nodes \(u\) and \(v\).

outputFormat

Output a single integer, the value of \(S\) modulo \(786433\).

sample

3
1 2 3
1 2
2 3

36