← 返回题目列表

Codeforces · 914/G

G. 斐波那契求和

中文机器翻译题面 查看原题

给定一个由 n 个非负整数组成的数组 s。

如果满足以下条件,则整数 5 元组 (a, b, c, d, e) 被认为是有效的:

- 1 ≤ a, b, c, d, e ≤ n
- (sa | sb) & sc & (sd ^ se) = 2i 对于某个整数 i
- sa & sb = 0

这里,'|'是按位或,'&' 是按位与,'^' 是按位异或运算。

求所有有效 5 元组 (a, b, c, d, e) 的 f(sa|sb) * f(sc) * f(sd^se) 之和,其中 f(i) 是第 i 个斐波那契数 (f(0) = 0, f(1) = 1, f(i) = f(i - 1) + f(i - 2))。

由于答案可能是巨大的输出,它模 109 + 7。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 106)。

输入的第二行包含 n 个整数 si (0 ≤ si < 217)。

输出

如上所述输出总和,模 109 + 7

示例

输入 #1

2
1 2

输出 #1

32

输入 #2

3
7 4 1

输出 #2

3520

输入 #3

10
1 3 0 7 3 7 6 5 7 5

输出 #3

1235424

输入#4

10
50 9 11 44 39 40 5 39 23 7

输出#4

113860062