Sum the Fibonacci

음이 아닌 정수 n개로 이루어진 배열 s가 주어진다.

정수 5-튜플 (a, b, c, d, e)이 다음 조건을 만족하면 유효하다고 한다:

• 1 ≤ a, b, c, d, e ≤ n
• 어떤 정수 i에 대해 (sa | sb) & sc & (sd ^ se) = 2i
• sa & sb = 0

여기서 '|'는 비트 단위 OR, '&'는 비트 단위 AND, '^'는 비트 단위 XOR 연산이다.

모든 유효한 5-튜플 (a, b, c, d, e)에 대한 f(sa|sb) * f(sc) * f(sd^se)의 합을 구하라. 여기서 f(i)는 i-th 피보나치 수이다. (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로 나눈 나머지를 출력한다.