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

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

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

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

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

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

第二行输入  个非负整数 ，表示各项费用。

- 对于  的评测用例，，。

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

3
0 2 5

11

对于输入样例中的三个数 ，所有可能的运算符组合共有  种。计算结果如下：











所有结果的总和为：



 对  取余后的值依然为 ，因此，输出结果为 。