Killjee is playing with an array a, which has n integers. He is trying to encrypt this array as a single integer.

Let l be the largest number in array a. Then, the code for array a is \(\sum_{j=0}^{l} b_j*31^j\) mod \(10^9+7\).

Here, \(b_j\) is the size of largest subset of array a whose XOR is equal to j.If there exist no subset of array a whose XOR is j then \(b_j = 0 \).

INPUT CONSTRAINTS:

\(1 \le n \le 10^4\)

\(1 \le a_i \le 10^3\)

INPUT FORMAT :

First line of input contains a single integer n. Next line contains n space separated integers, elements of array a.

OUTPUT FORMAT :

Print a single integer code of the array a.