Bob is having a array A of N elements . Bob wants to determine the beauty of the array and the beauty of the array is defned as :-
Determine Bitwise OR of maximum and minimum elements of every subset of size greater than or equal to 2 and add them.
As the answer can be quite large , you have to report it by taking modulo with 1000000007 .
Input
First line of the input will contain N , denoting the number of elements of the array.
Second line will contain N spaced integers denoting elements of the array .
Constraints
Output:
For each query you have to output single integer denoting beauty of the array .
Hint:
Hashing
Array contains 3 integers . Thus all subsets having size >= 2 are :-
{ { 2, 5 } , { 2 , 5} , {5 , 5} , {2 , 5 , 5 } } , thus bitwise OR of the maximum and minimum elements of those subsets are
{ 7 , 7 , 5 , 7 } respectively , thus summation of all is 7 + 7 + 5 + 7 = 26%1000000007 = 26 .