BADXOR  Bad XOR
Bad XOR  BADXOR
Time Limit: 1s
You are given an array A of N elements. Also you are given another array B of M elements. Any subset (i_{1}, i_{2}, i_{3}, …., i_{p }) is bad IFF ( Ai_{1} ⊕ Ai_{2} ⊕ …. ⊕ Ai_{p }) equals any value of B. ⊕ means Bitwise XOR, which can be found with ^ syntax in popular programming languages. Now your job is to find the number of good subsets. Empty Subset has XOR value of 0.
Input
The first line of input denotes the number of test cases T (1 <= T <= 20). The first line of each test case contains two integers N and M ( 0 <= N, M <= 1000). The next line contains N integers of the array A (0 <= A_{i }<=1000). The next line contains M integers of the array B (0 <= B_{i }<=1000). You can assume that each element of array B will be unique.
Output
For each case, print the case number and the total numbers of good subsets in a line. As the result can be very big, output it modulo 100000007.
Sample Input 
Output for Sample Input 
2 2 3 1 2 0 1 2 1 3 1 0 1 2 
Case 1: 1 Case 2: 0

Problem Setter: Nafis Sadique
Special Thanks: Ahmad Faiyaz
hide comments
Rafail Loizou:
20201106 00:55:52
I don't get why I get WA I check for case where n=0 but still. 

kishorevarma:
20200602 11:20:25
modulo is 1e8 +7 not 1e9+7 as in many questions. 

rising_stark:
20200428 00:50:40
@tungbean The maximum btw that you can get by XORing any number of elements of A is 1024.


rising_stark:
20200428 00:47:36
Can anyone tell me if array A contains duplicates like if A[]={1,1,1} and B={1}


dipta10:
20200424 03:18:33
There is something seriously wrong with the input. The value of $B_i$ is not within the range 0 to 1000. Have been staring at my solution for more than 2 hours straight, in the end I put values of $B_i$ in a set to check whether it exists and got AC. 

saurav_555:
20200327 11:11:18
Thanks for the comments!!!...


tungbean95:
20191225 04:59:47
When I set size of DP is 1030 and get WA. (1030 is the maximum value of (a[i1] ^ a[i2] ^ ... a[ip]))


maratha:
20190812 11:09:59
Don't forget to reset array B. 

dhruv2212000:
20190321 00:35:03
Awesome problem! Instead of finding good subsets find bad subsets and subtract them from total number of subsets :) 

ab_biswas09:
20190320 22:33:12
MY 100th 
Added by:  Faiyaz 
Date:  20131224 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 