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, 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.

 

                                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
ayush5148: 2017-08-15 21:25:05

Spoj toolkit for this question is WRONG .....
So , Be careful and believe in yourself !!

namitp: 2017-08-13 08:18:59

How Best Soln is in 0.01......strange....

blackjack123: 2017-07-29 14:08:02

commutative property of xor

nk17kumar: 2017-07-03 06:12:29

thanks to @yash_22 comment :)

sas1905: 2017-05-23 01:01:03

corner case n=0

kg93999: 2017-03-22 18:24:48

java tle
c++ AC
:(

aman224: 2017-03-16 09:26:05

Why modulo 100000007 and not 1000000007 ?
1 WA :/

lonewolf_1: 2017-02-28 11:31:14

10^8 + 7 modulo :)

yash_22: 2016-12-28 08:25:37

@aditya730 the constraints are not wrong. If a XOR b = c, then it is possible that c > a && c > b. For example 999 XOR 24 = 1023. You need to consider only till 1023 because the bit corresponding to 2**10 i.e. 1024 will never be set in the input and the XOR will never exceed 1023

aditya730: 2016-12-27 20:30:34

The constraints are all wrong.even with an array of 1020 got wa. More than 2 hours wasted due to this.And spoj toolkit is wrong for this one.Assume number of elements are 1025


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