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


hide comments
Rafail Loizou: 2020-11-06 00:55:52

I don't get why I get WA I check for case where n=0 but still.

kishorevarma: 2020-06-02 11:20:25

modulo is 1e8 +7 not 1e9+7 as in many questions.

rising_stark: 2020-04-28 00:50:40

@tungbean The maximum btw that you can get by XORing any number of elements of A is 1024.

rising_stark: 2020-04-28 00:47:36

Can anyone tell me if array A contains duplicates like if A[]={1,1,1} and B={1}
Then there will be 8 subsets in total but only 4 unique subsets.
So, the good subsets will be 4(considering duplicates as valid bad subsets) or 2(only unique).

The question states there are no duplicates in B but nothing about A.

Edit: Finally got AC by considering same looking subsets as different. So, answer to my test case above would be 4. Also, the size of dp array should be [n+1][1024]

Last edit: 2020-04-28 03:30:55
dipta10: 2020-04-24 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: 2020-03-27 11:11:18

Thanks for the comments!!!...
It's help me to find :
1. mistakes
2. edge cases..
3. some test cases..

Last edit: 2020-03-27 11:11:46
tungbean95: 2019-12-25 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]))
But when i set the size is 10010, i get AC ==
I think there are some tests that the limit of size A or B is over 1000 or value of A[i] is over 1000.
Please check the testcase.
Thank you.
By the way, it 's a interesting problem.

maratha: 2019-08-12 11:09:59

Don't forget to reset array B.

dhruv2212000: 2019-03-21 00:35:03

Awesome problem! Instead of finding good subsets find bad subsets and subtract them from total number of subsets :)

ab_biswas09: 2019-03-20 22:33:12

MY 100th


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