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

\(1 \le N \le 200000\)

\(1 \le A [ I ] \le 1000\)

Output:

For each query you have to output single integer denoting beauty of the array .

Hint:

Hashing