题目描述

老王计划装修房子，于是联系了一家装修公司。该公司有一套自动报价系统，只需用户提供 $N$ 项装修相关费用 $A_1, A_2, \dots , A_N$，系统便会根据这些费用生成最终的报价。

然而，当老王提交数据后，他发现这套系统的运作方式并不透明：系统只会给出一个最终报价，而不会公开任何运算过程或中间步骤。

公司对此解释称，这套系统会依据某种内部算法，在每对相邻数字之间插入 $+$（加法）、$-$（减法）或 $\oplus$（异或）运算符，并按照特定优先级规则计算结果：异或运算优先级最高，其次是加减。但由于保密性，具体的运算符组合以及中间过程都不会对外公开。

为了验证系统报价是否合理，老王决定模拟其运作方式，尝试每种可能的运算符组合，计算出所有可能出现的结果的总和。如果最终报价明显超出这个范围，他就有理由怀疑系统存在异常或误差。只是老王年事已高，手动计算颇为吃力，便向你求助。

现在，请你帮老王算出所有可能的结果的总和。由于该总和可能很大，你只需提供其对 $10^9+7$ 取余后的结果即可。

输入格式

第一行输入一个整数 $N$，表示装修相关费用的项数。

第二行输入 $N$ 个非负整数 $A_1, A_2, \dots , A_N$，表示各项费用。

输出格式

输出一个整数，表示所有可能的总和对 $10^9 + 7$ 取余后的结果。

3
0 2 5

11

提示

对于输入样例中的三个数 $A = [0, 2, 5]$，所有可能的运算符组合共有 $9$ 种。计算结果如下：

$$0 \oplus 2 \oplus 5 = 7$$ $$0 \oplus 2 + 5 = 7$$ $$0 \oplus 2 - 5 = -3$$ $$0 + 2 \oplus 5 = 7$$ $$0 + 2 + 5 = 7$$ $$0 + 2 - 5 = -3$$ $$0 - 2 \oplus 5 = -7$$ $$0 - 2 + 5 = 3$$ $$0 - 2 - 5 = -7$$

所有结果的总和为：

$$7 + 7 + (-3) + 7 + 7 + (-3) + (-7) + 3 + (-7) = 11 $$

$11$ 对 $10^9 + 7$ 取余后的值依然为 $11$，因此，输出结果为 $11$。

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1 \leq N \leq 13$，$0 \leq A_i \leq 10^3$。
• 对于 $60\%$ 的评测用例，$1 \leq N \leq 10^3$，$0 \leq A_i \leq 10^5$。
• 对于 $100\%$ 的评测用例，$1 \leq N \leq 10^5$，$0 \leq A_i \leq 10^9$。