题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$。

你需要把这个序列划分成若干段，定义一段的权值是这一段中所有数的异或和，定义一个划分方案的权值是所有段的权值之积。

求所有划分方案的权值和，对 $10^9+7$ 取模。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

输出一行一个整数表示答案，

样例

样例输入

4
7 3 1 2

样例输出

170

• |7,3,1,2| 权值是 $7$。
• |7|3,1,2| 权值是 $7 \times 0 = 0$
• |7,3|1,2| 权值是 $4 \times 3 =12$
• |7,3,1|2| 权值是 $5 \times 2 = 10$。
• |7,3|1|2| 权值是 $4 \times 1 \times 2 = 8$
• |7|3,1|2| 权值是 $7 \times 2 \times 2 = 28$
• |7|3|1,2| 权值是 $7 \times 3 \times 3 = 63$
• |7|3|1|2| 权值是 $7 \times 3 \times 1 \times 2 = 42$
• 答案是 $7+0+12+10+8+28+63+42=170$

数据范围与约定

对于所有数据，有：

• $1 \le n \le 3 \times 10^5$
• $0 \le a_i \le 10^{18}$