CF914G.Sum the Fibonacci

You are given an array s of n non-negative integers.

A 5-tuple of integers (a, b, c, d, e) is said to be valid if it satisfies the following conditions:

• 1 ≤ a, b, c, d, e ≤ n
• (s__a | s__b) & s__c & (s__d ^ s__e) = 2_i_ for some integer i
• s__a & s__b = 0

Here, '|' is the bitwise OR, '&' is the bitwise AND and '^' is the bitwise XOR operation.

Find the sum of f(s__a|s__b) * f(s__c) * f(s__d^s__e) over all valid 5-tuples (a, b, c, d, e), where f(i) is the i-th Fibonnaci number (f(0) = 0, f(1) = 1, f(i) = f(i - 1) + f(i - 2)).

Since answer can be is huge output it modulo 109 + 7.

给你一个长度为 $ n $ 的非负整数数组 $ s $。

一个五元组整数 $ (a,,b,,c,,d,,e) $ 被称为合法的，当且仅当它满足以下条件：

• $ 1 \leq a,,b,,c,,d,,e \leq n $
• $ (s_a \mid s_b) ,&, s_c ,&, (s_d \oplus s_e) = 2^i $，其中 $ i $ 为某个整数
• $ s_a ,&, s_b = 0 $

其中，$ \mid $ 表示按位或（bitwise OR），$ & $ 表示按位与（bitwise AND），$ \oplus $ 表示按位异或（bitwise XOR）。

对所有合法的五元组 $ (a,,b,,c,,d,,e) $，求

$$f(s_a \mid s_b) \cdot f(s_c) \cdot f(s_d \oplus s_e)$$

的总和，其中 $ f(i) $ 表示第 $ i $ 个斐波那契数（定义为：$ f(0) = 0 $，$ f(1) = 1 $，$ f(i) = f(i-1) + f(i-2) $）。

由于答案可能非常大，请将结果对 $ 10^9 + 7 $ 取模后输出。

The first line of input contains an integer n (1 ≤ n ≤ 106).

The second line of input contains n integers s__i (0 ≤ s__i < 217).

输入的第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）。

输入的第二行包含 $n$ 个整数 $s_i$（$0 \leq s_i < 2^{17}$）。

Output the sum as described above, modulo 109 + 7

按上述要求输出总和，对 $10^9 + 7$ 取模。