题目描述

小 X 给了你一棵 $n$ 个点的树，点有点权。

你需要求出下列式子模 $786433$ 的值：

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

其中 $f(u,v)$ 表示 $u$ 到 $v$ 的最短路径上所有点的点权按位与在一起之后的值。

提示：为了方便你的计算，这里我们认为 $0^0=0$。另外，$786433$ 是一个质数，同时也是一个不常用的 NTT 模数，它的原根为 $10$，如果你不知道什么是 NTT 或者不知道什么是原根，你可以忽略这个提示。

输入格式

第一行一个正整数 $n$，表示树的点数。

第二行 $n$ 个正整数 $a_{1\dots n}$，其中 $a_i$ 表示编号为 $i$ 的点的点权。

接下来 $n-1$ 行，每行 $2$ 个正整数 $u,v$，表示编号为 $u$ 和编号为 $v$ 的点之间有一条边。

数据范围：

• $2 \le n \le 2 \times 10^5$。
• 对于所有满足 $1\le i \le n$ 的 $i$ 都有 $1 \le a_i < 2^{30}$。
• $1 \le u,v \le n, u \ne v$。
• 设 $d$ 为树中叶子（度数为 $1$ 的点）的个数，数据保证 $4\le n \cdot d \le 3 \times 10 ^ 6$。

输出格式

一行一个整数，表示答案对 $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