CF2174F Mosaic Tree

The master creates a composition of $ n $ colored mosaic elements. Each element is painted in one of $ m $ possible colors (the colors are numbered from $ 1 $ to $ m $ ). The master arranges the composition in such a way that it can be represented as a tree. The composition is considered beautiful if for each color $ i $ , the total degree of all vertices of color $ i $ has a specified parity $ \mathrm{mask}_i $ , where $ \mathrm{mask} $ is an array of $ m $ numbers $ 0 $ or $ 1 $ . Help the master count the number of ways to create a beautiful composition. Output the answer modulo $ 10^9 + 7 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 10^4 $ ) — the number of vertices and the number of possible colors, respectively. The second line of each test case contains $ n $ integers $ c_i $ ( $ 1 \le c_i \le m $ ) — the color of vertex $ i $ . The third line of each test case contains $ m $ integers $ \mathrm{mask}_i $ ( $ \mathrm{mask}_i \in \{0, 1\} $ ) — the parity of color $ i $ (if the total degree of vertices of color $ i $ should be even, $ \mathrm{mask}_i = 0 $ , otherwise — $ \mathrm{mask}_i = 1 $ ). It is guaranteed that the sum of the values of $ n $ across all test cases does not exceed $ 10^4 $ , and it is also guaranteed that the sum of the values of $ m $ across all test cases does not exceed $ 10^4 $ .

For each test case, output a single integer on a separate line — the number of ways to create a beautiful composition modulo $ 10^9 + 7 $ .

In the first test case, a valid example of a tree would be described by the edges $ \{(1, 2), (1, 3), (1, 4)\} $ . Here, the degrees are $ 3, 1, 1, 1 $ respectively. Here, the total degree of vertices with colour $ 1 $ is $ 4 $ which is $ 0 $ mod $ 2 $ , and similarly, the total degree of vertices with colour $ 2 $ is $ 2 $ which is also $ 0 $ mod $ 2 $ , as required by the statement. An example of an invalid tree would be described by the edges $ \{(1, 2), (2, 3), (3, 4)\} $ as vertices with colour $ 1 $ have degrees adding to $ 3 $ , which is odd.