You are given the following :-
— An array A of length N
— An integer X
Task
Determine the number of sub-sequences of Array A such that the following condition is satisfied.
— If i1,i2....ik is the indices in the sub-sequence, then ( A[i1] ^ A[i2] ^.....^A[ik] ) & X =0, where ^ represents Bitwise XOR and & represent Bitwise AND operator.
Since, the number of sub-sequences can be large enough, output it modulo 10^9+7.
Example:-
Assumptions
- N = 4
- X = 7
- A[] = [5,2,7,6]
Output:-
2 , one is [5,2,7] another Empty sub-sequence.
Constraints
- 1<= N <= 1000
- 1<= X <= 1000
- 0<= A[i] <= 1000
Sample Input:-
3
1
5 7 1
Sample Output:-
4
