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
aman_sachin200:
20180524 21:30:07
Read the modulo and the output format carefully!Cost me 4 WAs :( 

bluejam:
20180521 05:00:41
Corner Case n=0


pranjal_27:
20180102 10:15:38
Just do not try Spoj Toolkit for this question .... Most of the test cases are wrong ... Keep belive in yourself ... :)


kspoj:
20171216 07:02:10
changed table size to [n+1][2000] and it got accepted :P


ayush5148:
20170815 21:25:05
Spoj toolkit for this question is WRONG .....


namitp:
20170813 08:18:59
How Best Soln is in 0.01......strange.... 

blackjack123:
20170729 14:08:02
commutative property of xor 

nk17kumar:
20170703 06:12:29
thanks to @yash_22 comment :) 

sas1905:
20170523 01:01:03
corner case n=0 

kg93999:
20170322 18:24:48
java tle

Added by:  Faiyaz 
Date:  20131224 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 