BADXOR - Bad XOR

You are given an array A of N elements. Also you are given another array B of M elements. Any subset (i­1, i2, i3 ... ip) is bad IFF (Ai1 ⊕ Ai2 ⊕ ... ⊕ Aip) 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 ≤ Ai ≤ 1000). The next line contains M integers of the array B (0 ≤ Bi ≤ 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.

Example

Input:
2
2 3
1 2
0 1 2
1 3
1
0 1 2

Output:
Case 1: 1
Case 2: 0

Problem Setter: Nafis Sadique, Special Thanks: Ahmad Faiyaz


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

hide comments
2016-11-16 19:43:53 Mauro Persano
If you're getting WA and can't figure out why: don't forget the empty set!
2016-09-08 10:32:10 Hasit Bhatt
I don't get it. If I add the number of ways when we don't get value B, it gives WA. But when I deduct the sum of possible ways to get B as XOR for total possible sets, my solution gets accepted. :/
2016-08-08 21:50:40
Something out of the box! :)
2016-08-03 16:31:44
I used 1023 instead of 1000 as boundary and it worked
2016-03-01 14:40:46
quite different, loved it !!!!
2016-01-22 20:20:44
huh ... 10^8 + 7 :(
2015-12-30 14:46:10 Govind Lahoti
Nice problem :)
2015-12-21 00:29:37 Daniel
Pardon my ignorance, but, what does the "TIME" column from each submission mean? The whole batch of test cases or the one which took the longest? Because my solution resulted in accepted with time 1.02s > 1s of time limit lol.
2015-12-18 06:45:36 Gautam Singh
I think the test cases are weak. My ACed solution and a solution from spojtoolkit (http://www.spojtoolkit.com/test/BADXOR) give different answers for a test case.
2015-12-11 04:51:13 Shubham Jain
Nice one :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.