CF914G Sum the Fibonacci

给定一个包含 $n$ 个非负整数的数组 $s$。 如果一个整数五元组 $(a, b, c, d, e)$ 满足以下条件，则称其为合法五元组： - $1 \leq a, b, c, d, e \leq n$ - $(s_{a} | s_{b}) \ \& \ s_{c} \ \& \ (s_{d} \oplus s_{e}) = 2^{i}$，其中 $i$ 是某个整数 - $s_{a} \ \&\ s_{b} = 0$ 其中，'|' 表示按位或，'&' 表示按位与，'^' 表示按位异或运算。 请你计算所有合法五元组 $(a, b, c, d, e)$ 的 $f(s_{a} | s_{b}) \times f(s_{c}) \times 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$ 取模后的结果。

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）。 第二行包含 $n$ 个整数 $s_{i}$（$0 \leq s_{i} < 2^{17}$）。

输出按要求计算的结果，对 $10^9+7$ 取模后的值。

由 ChatGPT 5 翻译