老王计划装修房子，于是联系了一家装修公司。该公司有一套自动报价系
统，只需用户提供 N 项装修相关费用 A1, A2, . . . , AN，系统便会根据这些费用生
成最终的报价。
然而，当老王提交数据后，他发现这套系统的运作方式并不透明：系统只
会给出一个最终报价，而不会公开任何运算过程或中间步骤。
公司对此解释称，这套系统会依据某种内部算法，在每对相邻数字之间插
入 +（加法）、−（减法）或 ⊕（异或）运算符，并按照特定优先级规则计算结
果：异或运算优先级最高，其次是加减。但由于保密性，具体的运算符组合以
及中间过程都不会对外公开。
为了验证系统报价是否合理，老王决定模拟其运作方式，尝试每种可能的
运算符组合，计算出所有可能出现的结果的总和。如果最终报价明显超出这个
范围，他就有理由怀疑系统存在异常或误差。只是老王年事已高，手动计算颇
为吃力，便向你求助。
现在，请你帮老王算出所有可能的结果的总和。由于该总和可能很大，你
只需提供其对 109 + 7 取余后的结果即可。