Bob and Beauty of the Array
Basic programming
Basics of implementation
Hash maps
Implementation
Medium
71.0% success
5,223 attempts
1s time
256MB memory
1024KB max code

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

Examples
Input
3
2 5 5
Output
26
Explanation

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 .

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...