试题 H: 装修报价

• 时间限制: 1.0s
• 内存限制: 256.0MB
• 本题总分: 20 分

【问题描述】

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

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

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

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

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

【输入格式】

• 第一行输入一个整数 N，表示装修相关费用的项数。
• 第二行输入 N 个非负整数 A₁,A₂,…,Aₙ，表示各项费用。

【输出格式】

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

【样例输入】

3
0 2 5

【样例输出】

11

【样例说明】

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

• 0⊕2⊕5 = 7,
• 0⊕2 + 5 = 7,
• 0⊕2 - 5 = -3,
• 0 + 2⊕5 = 7,
• 0 + 2 + 5 = 7,
• 0 + 2 - 5 = -3,
• 0 - 2⊕5 = -7,
• 0 - 2 + 5 = 3,
• 0 - 2 - 5 = -7.

所有结果的总和为： 7 + 7 + (-3) + 7 + 7 + (-3) + (-7) + 3 + (-7) = 11

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

【评测用例规模与约定】

• 对于 30% 的评测用例，1 ≤ N ≤ 13，0 ≤ Aᵢ ≤ 10³。
• 对于 60% 的评测用例，1 ≤ N ≤ 10³，0 ≤ Aᵢ ≤ 10⁵。
• 对于 100% 的评测用例，1 ≤ N ≤ 10⁵，0 ≤ Aᵢ ≤ 10⁹。