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

Input

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

Output

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

Note

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.

✓	#	Name		✎	Rating↕	Solved↕
	2174F	Mosaic Tree combinatorics dp fft math trees			2800	508
	1408G	Clusterization Counting combinatorics dp dsu fft graphs trees			2700	1.4k

Problemset