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.
4 1 2 3 4
3755653
Here, \( b[0]=3 \) as the subset \((1,2,3)\) has xor value equal to 0.
\(b[1]\)=2, as the subset \((2,3)\) has xor value equal to 1
\( b[2] \) = 2, as the subset \((1,3)\) has xor value equal to 2
\(b[3]\)=2, as the subset \((1,2)\) has xor value equal to 3
\(b[4]\) = 4, as the subset \((1,2,3,4)\) has xor value equal to 4.
Thus, the answer = \( (b[0] \times 31^0) + (b[1] \times 31^1) + (b[2] \times 31^2) + (b[3] \times 31^3) + (b[4] \times 31^4 )\) Modulo \( 10^9+7 \) = \(3755653\) .
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
Login to unlock the editorial
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