给定一个整数序列 $a_1, a_2, \dots, a_n$。序列 $a_1, a_2, \dots, a_n$ 的一个划分定义为一组连续的区间，使得每个元素恰好属于其中一个区间。

序列中一个连续区间的异或和定义为该区间内所有数字的按位异或（bitwise xor）结果。一个划分的权值定义为该划分中所有区间异或和的乘积。计算所有可能的划分的权值之和。由于该数字可能非常大，只需输出其对 $10^9 + 7$ 取模后的余数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3 \cdot 10^5$)，表示序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{18}$)，表示该序列。

输出格式

输出一个整数，表示所有可能的划分的权值之和对 $10^9 + 7$ 取模后的余数。

样例

输入 1

4
7 3 1 2

输出 1

170

说明

序列的可能划分如下：

• $[7, 3, 1, 2]$ – 权值为 $7$
• $[7, 3], [1, 2]$ – 权值为 $4 \cdot 3 = 12$
• $[7], [3, 1, 2]$ – 权值为 $7 \cdot 0 = 0$
• $[7, 3, 1], [2]$ – 权值为 $5 \cdot 2 = 10$
• $[7, 3], [1], [2]$ – 权值为 $4 \cdot 1 \cdot 2 = 8$
• $[7], [3], [1, 2]$ – 权值为 $7 \cdot 3 \cdot 3 = 63$
• $[7], [3, 1], [2]$ – 权值为 $7 \cdot 2 \cdot 2 = 28$
• $[7], [3], [1], [2]$ – 权值为 $7 \cdot 3 \cdot 1 \cdot 2 = 42$

所有划分的权值之和为 $7 + 12 + 0 + 10 + 8 + 63 + 28 + 42 = 170$。