题目描述

Romeo 所在的社区可以看成一棵有 $N$ 个结点的树，每个结点住着一位朋友。第 $i$ 个结点上的朋友有一个价值 $v_i$。

Romeo 每次会先选出一个非空朋友集合，作为本次要拜访的名单。为了拜访这些朋友，他会沿树上的最短道路移动；等价地，他实际经过的结点集合为：包含所选朋友集合的、结点数最少的连通子树，记为 $S$。

走完以后，Romeo 会在经过的所有结点中，额外停留在价值最小的朋友处。也就是说，他会选择子树 $S$ 中价值最小的一个结点。若有多个价值同为最小的结点，Romeo 只选择其中一个。若这个结点本来就在拜访名单中，则它会被“访问两次”。

若 Romeo 原本选择拜访的结点为 $n_1,n_2,\ldots,n_k$，额外停留的最小价值结点为 $n_{min}$，则本次行程的价值定义为

$$v_{n_1}\oplus v_{n_2}\oplus\cdots\oplus v_{n_k}\oplus v_{n_{min}},$$

其中 $\oplus$ 表示按位异或。

现在 Romeo 想象自己会选择所有可能的非空朋友集合。请你求出所有这些行程价值之和，并对 $10^9+7$ 取模。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $v_1,v_2,\ldots,v_N$，其中 $v_i$ 表示结点 $i$ 上朋友的价值。

接下来 $N-1$ 行，每行两个整数 $x,y$，表示树上有一条连接 $x$ 与 $y$ 的边。

输出格式

输出一个整数，表示所有非空子集对应行程价值之和，对 $10^9+7$ 取模后的结果。

数据范围与子任务

• $1\le N\le 200000$
• $0\le v_i\le 1000000000$
• 15 分：$N\le 15$
• 25 分：$N\le 5000$
• 15 分：$N\le 20000$
• 15 分：$N\le 70000$

样例输入1

3
7 3 2
1 2
2 3

样例输出1

21

样例解释

树为链 $1-2-3$，三个结点的价值分别为 $7,3,2$。

所有非空子集的行程价值如下：

• $\{1\}$：$7\oplus 7=0$
• $\{2\}$：$3\oplus 3=0$
• $\{3\}$：$2\oplus 2=0$
• $\{1,2\}$：最小值在结点 $2$，价值 $7\oplus 3\oplus 3=7$
• $\{2,3\}$：最小值在结点 $3$，价值 $3\oplus 2\oplus 2=3$
• $\{1,3\}$：经过 $1,2,3$，最小值在结点 $3$，价值 $7\oplus 2\oplus 2=7$
• $\{1,2,3\}$：最小值在结点 $3$，价值 $7\oplus 3\oplus 2\oplus 2=4$

总和为 $0+0+0+7+3+7+4=21$。

样例输入2

3
1 1 1
1 3
2 3

样例输出2

3

样例输入3

5
1 3 7 2 5
1 2
2 3
2 4
4 5

样例输出3

98