给定一个由 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