生日

题号：NC236627
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

共有 $n$ 个人，分别编号为 $1 \sim n$ ，每一个人都有一个属性值，其中第 $i$ 个人的属性值为 $a_i$ 。如果有两个编号为 $i,j$ 的人在同一天过生日，则他们两个人会产生 $a_i \oplus a_j$ 的快乐值，其中 $\oplus$ 是位运算中的异或运算符。同理，若三个人或更多人在同一天过生日，则这些人产生的快乐值是所有在这一天过生日的人的异或值。若某一个人单独过生日，则不产生任何快乐值。

为了使得公历生日不同的鸡尾酒和玥玥也可以在同一天过生日，鸡尾酒规定每个人有两个生日，一个公历生日，一个农历生日，且可以在这两天中任选一天进行“过生日”活动。现在我们假设第 $i$ 个人的公历生日为第 $i$ 天，农历生日为第 $\lfloor \frac{i}{2} \rfloor$ 天（其中 $\lfloor x \rfloor$ 表示对 $x$ 向下取整）。那么这 $n$ 个人会有很多种不同的过生日方案，现在鸡尾酒想问你所有过生日方案的所有快乐值之和是多少？

两种过生日方案不同当且仅当存在某一个人 $i$ 在两种方案中选择了不同的一天进行过生日。
由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

输入描述:

输入第一行包含一个正整数 ，表示总人数。

接下来包含  个数字 ，表示每一个人的属性值。

输出描述:

输出一行一个整数表示答案对  取模后的结果。

示例1

输入

复制

3
1 3 4

输出

复制

说明

共有三个人，第  个人的生日是第  天或第  天。即第一个人的生日是第 0/1 天，第二个人的生日是第 1/2 天，第三个人的生日是第 1/3 天
用 [1,2,3] 表示第一个人在第一天过生日，第二个人在第二天过生日，第三个人在第三天过生日。此时没有任何两个人一起过生日，所以快乐值为 0。
[1,1,1] 表示三个人都在第一天过生日，此时产生的快乐值为 6（1、3、4 三个数字的异或值）
[0,1,1] 快乐值为 7。
[1,1,3] 快乐值为 2。
[1,2,1] 快乐值为 5。
其余过生日方案的快乐值都为 0，因为这些方案中没有任何两个人在同一天过生日。
求和得到 20。

示例2

输入

复制

4
1 2 3 4

输出

复制

说明

[1,2,1,2] 表示第一个人和第三个人在第一天过生日，产生的快乐值为 ；第二个和第四个人都在第二天过生日，产生的快乐值为 ，所以这一种方案共产生快乐值为 6 + 2 = 8。
[1,2,3,2]、[0,2,3,2]、[0,2,1,2] 这三种方案都只有第二个和第四个人一起过生日，产生快乐值都为 6，三种方案快乐值共计 6*3=18。
[1,2,1,4] 产生快乐值为 2。
[1,1,1,4]、[1,1,1,2] 这两种方案是前三个人一起过生日，但是 ，所以这三种方案产生的快乐值为 0。
[0,1,1,4]、[0,1,1,2] 的快乐值均为 1，两种方案共计 2*1=2。
[1,1,3,4]、[1,1,3,2] 的快乐值均为 3，两种方案共计 3*2=6。
其余方案的快乐值为 0，以上所有方案快乐值之和为 8+18+2+2+6=36