Create Sum of XOR of all subsets.cpp

Given a list containing N integers, calculate the XOR_SUM of all the non-empty subsets of the list and print the value of sum % (109 + 7).

XOR operation on a list (or a subset of the list) is defined as the XOR of all the elements present in it. 
E.g. XOR of list containing elements {A,B,C} = ((A^B)^C), where ^ represents XOR.

E.g. XOR_SUM of list A having three elements {X1, X2, X3} can be given as follows.
All non-empty subsets will be {X1, X2, X3, (X1,X2), (X2,X3), (X1,X3), (X1,X2,X3)}

XOR_SUM(A) = X1 + X2 + X3 + X1^X2 + X2^X3 + X1^X3 + ((X1^X2)^X3)

Input Format
An integer T, denoting the number of testcases. 2T lines follow.
Each testcase contains two lines, first line will contains an integer N followed by second line containing N integers separated by a single space.

Solution:
    In any subset, the ith bit will be set, only if it is made of numbers out of which atleast one has ith bit set.
    Now, let there are a numbers be with ith bit set, and b = n-a with ith bit not set.
    Now, without loss of generality, let a be even, taking one of the numbers out, there will be a-1(m) number left.
    Now, the number taken out will be a part of 2^(n-1) subsets, so for these subests we have to take even combinations from a-1 numbers.
    From the other 2^(n-1) subsets we have to take odd combinations.
    Also, the ith bit contributes to 2^i.
    So, total contribution in the whole sun becomes
        2^i*2(b)*((mc0+mc2+mc4..) + (mc1+mc3+mc5...))
        2^(N-1+i)
    Summing over all i's the solution becomes,
        2^(N-1)*(OR of all numbers).