当前没有测试数据。

问题描述

牛可乐有一棵由 $n$ 个结点构成的树，第 $i$ 个节点的权值为 $a_i$。我们定义一个连通块 $\Bbb V$ 的权值为：

• 当前连通块中两两结点的权值异或和，即 $\sum \limits_{i,j \in \Bbb V} (a_i \oplus a_j)$。

你需要计算全部连通块的权值之和。由于答案可能很大，请将答案对 $(10^9 + 7)$ 取模后输出。

此题中的连通块定义为：对于树上的任意一个点集 $\Bbb S$，如果 $\Bbb S$ 中的任意两点 $u, v$ 之间存在一条路径，且路径上的所有点都在 $\Bbb S$ 中，则称 $\Bbb S$ 是一个连通块。

输入格式

• 第一行输入一个整数 $n$（$1 \leq n \leq 10^5$），代表树上的节点数量。
• 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），代表每个节点的权值。
• 此后 $n-1$ 行，第 $i$ 行输入两个整数 $u_i, v_i$（$1 \leq u_i, v_i \leq n, u_i \neq v_i$），代表树上第 $i$ 条边连接节点 $u_i$ 和 $v_i$。

输出格式

输出一个整数，代表全部连通块的权值和。答案可能很大，请将答案对 $(10^9 + 7)$ 取模后输出。

示例

示例 1：

输入：

3
5 2 1
1 2
1 3

输出：

50

说明：

• 在这个样例中，一共有 $6$ 个连通块，每一个连通块的权值依次为：
  • $\{1\}$，记为 $\Bbb V_1$，权值为 $\sum\limits_{i,j \in \Bbb V_1}$$(a_i \oplus a_j) = a_1 \oplus a_1 = 0$；
  • $\{1,2\}$，记为 $\Bbb V_2$，权值为 $\sum\limits_{i,j \in \Bbb V_2}$$(a_i \oplus a_j) = (a_1 \oplus a_1) +$$(a_1 \oplus a_2) + (a_2 \oplus a_1) +$$(a_2 \oplus a_2) = 14$；
  • $\{1,3\}$，记为 $\Bbb V_3$，权值为 $\sum\limits_{i,j \in \Bbb V_3}$$(a_i \oplus a_j) = (a_1 \oplus a_1) +$$(a_1 \oplus a_3) + (a_3 \oplus a_1) +$$(a_3 \oplus a_3) = 8$；
  • $\{1,2,3\}$，记为 $\Bbb V_4$，权值为 $ \sum\limits_{i,j \in \Bbb V_4} (a_i \oplus a_j) = 28 $；
  • $\{2\}$，记为 $\Bbb V_5$，权值为 $\sum\limits_{i,j \in \Bbb V_5}$$(a_i \oplus a_j) = a_2 \oplus a_2 = 0$；
  • $\{3\}$，记为 $\Bbb V_6$，权值为 $\sum\limits_{i,j \in \Bbb V_6}$$(a_i \oplus a_j) = a_3 \oplus a_3 = 0$。
• 所以，全部连通块的权值和为 $0 + 14 + 8 + 28 + 0 + 0 = 50$。

示例 2：

输入：

4
5 6 3 1
1 2
1 3
2 4

输出：

142