So after successfully becoming many people's nightmare, XOR has struck again, this time to haunt you on a tree!!! You are given a tree with N vertices. The vertices are numbered from 1 to N. Each vertices holds a non-negative integer value. You are also given a set of non-negative integers, these integers are bad. The values of each vetices of the tree and the set are less than 501.You need to find out the number of non-empty subtrees of the given tree such that the XOR of all the values of the vertices of the subtree doesn't exist in the given set.
What is a subtree? A subtree of a tree is a set of vertices, such that there is a path from every vertex of the set to every other vertices of the set consisting of only the vertices from the set (see the explanation to make the concept of subtrees more clear).
The XOR of some values is the bitwise xor of all the values. Suppose you have 3 values {1, 2, 5}, then their XOR value would be 6.
The first line of the input contains an integer T (1 <= T <= 20). Then T tests follows. The first line of each test case starts with two integers N (1 <= N <= 100) and M, M is the size of the set of bad values. Then N-1 lines each contains two integers, providing the endpoints of an edge of the tree. The next line contains N integers, the values of each of the vertices in the order of their number. The next line contains M distinct integers. These values are the elements of the set. The given tree is valid.
For each test case, print the case number followed by the number of different subtrees. This value can be quite big so print the result modulo 1000000007 (it is 10^9+7 this time). Follow the sample I/O for details.
| Input | Output |
|---|---|
2 3 3 1 2 1 3 1 1 2 0 3 1 2 0 1 2 500 500 | Case 1: 2 Case 2: 3 |
For the first test, the different subtrees are { {1}, {2}, {3}, {1,2}, {1,3}, {1,2,3} }, the XOR of each of the subtrees are { 1, 1, 2, 0, 3, 2 } correspondingly. Among them the subtrees { {3}, {1,2,3} } will give XOR value which doesn't exist in the bad set.
For the second test, there is no bad set. So all three subtrees are valid.