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*) &amp; *s**c* &amp; (*s**d* ^ *s**e*)<==<=2*i* for some integer *i* -  *s**a* &amp; *s**b*<==<=0 
Here, '|' is the bitwise OR, '&amp;' 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.
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*<=&lt;<=217).
Output the sum as described above, modulo 109<=+<=7
none