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.