Given an array of N numbers, for each subset of the array Little Panda performs MAXOR operation for the subset.MAXOR operation means that he finds XOR of all elements in that subset (if the subset is [1,2,3] then MAXOR is 1^2^3=0) . Little Panda is now exhausted and wants to do something else. Little Panda wants to pick any two subsets the MAXORof whose are same. Little Panda needs to find the number of selections that he can make. He is very very weak in programming so he wants the answer from you. Please help little panda in finding out his query.
Since the output can be very large output it modulo 1000000007.
The first line contains N i.e. the length of the array.
N lines follow, each containing a non-negative integer.
Output Little Panda's Query in a single line.
1 <= N <= 100000
0 <= A[i] <= 100
(where A[i] denotes the value of array element)
# Finding the count of subsets, such that each subset MAXOR is x in
def FindSubsetCount(array,n):
maxOrCount = [0]*128 # array to store MAXOR Count frequencies
maxOrCount[0] = 1 # Assuming null subset sum = 1
for i in range(0,n):
element = array[i]
changeCount=[0]*128
for j in range(0,128):
changeCount[j^element] += maxOrCount[j]
for j in range(0,128):
maxOrCount[j] += changeCount[j]
maxOrCount[j] %= 1000000007
maxOrCount[0] -= 1 # remove as the panda does not know about the null subset
return TotalCombinations(maxOrCount)
def TotalCombinations(maxOrCount):
threshold = 1000000007
totalCombinations = 0
for i in range(0,128):
subsetCount = maxOrCount[i]
if subsetCount > 0:
totalCombinations += ((subsetCount*(subsetCount-1))/2)
if totalCombinations >= threshold:
totalCombinations %= threshold
return totalCombinations
def run():
try:
# collect number of input elements
n = int(raw_input())
if n < 1 or n > 100000:
return
# collect input elements
a = [0]*n
#a = map(int, raw_input().split())
for i in range(0,n):
a[i] = int(raw_input())
if a[i] < 0 or a[i] > 100:
return
print FindSubsetCount(a,n)
except:
return
if __name__ == "__main__":
run()