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

大师创作一幅由 $n$ 个彩色马赛克元素构成的作品。每个元素被涂上 $m$ 种可能颜色之一（颜色编号为 $1$ 到 $m$）。

大师将作品以树的形式进行排布。

若对每种颜色 $i$，所有颜色为 $i$ 的顶点的度数总和具有指定的奇偶性 $\mathrm{mask}_i$，则该作品被称为“优美的”。其中 $\mathrm{mask}$ 是一个长度为 $m$ 的数组，每个元素为 $0$ 或 $1$。

请帮助大师计算创作一幅优美作品的方案数。答案对 $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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^4$）—— 分别表示顶点数量和可能的颜色数量。

每个测试用例的第二行包含 $n$ 个整数 $c_i$（$1 \le c_i \le m$）—— 表示顶点 $i$ 的颜色。

每个测试用例的第三行包含 $m$ 个整数 $\mathrm{mask}_i$（$\mathrm{mask}_i \in \{0, 1\}$）—— 表示颜色 $i$ 的奇偶性（若颜色 $i$ 的所有顶点的总度数应为偶数，则 $\mathrm{mask}_i = 0$；否则 $\mathrm{mask}_i = 1$）。

保证所有测试用例中 $n$ 的总和不超过 $10^4$，且所有测试用例中 $m$ 的总和也不超过 $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$.

对于每个测试用例，在单独一行中输出一个整数——构造优美组合的方案数对 $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.

在第一个测试用例中，一棵合法的树的一个有效示例由边集 $\{(1, 2), (1, 3), (1, 4)\}$ 描述。此时各顶点的度数分别为 $3, 1, 1, 1$。其中，颜色为 $1$ 的顶点的度数之和为 $4$，满足模 $2$ 余 $0$；类似地，颜色为 $2$ 的顶点的度数之和为 $2$，同样满足模 $2$ 余 $0$，符合题意要求。

一个非法树的示例如下：其边集为 $\{(1, 2), (2, 3), (3, 4)\}$，此时颜色为 $1$ 的顶点的度数之和为 $3$，是奇数，不满足要求。