CF2174F Mosaic Tree

大师制作了一幅由 $n$ 个彩色马赛克元素组成的作品。每个元素被涂成 $m$ 种可能颜色中的一种（颜色编号为 $1$ 到 $m$）。 大师将作品排列成能够表示为一棵树的形式。 如果对于每种颜色 $i$，所有颜色为 $i$ 的顶点的度数之和具有指定的奇偶性 $\mathrm{mask}_i$，则称该作品是美丽的，其中 $\mathrm{mask}$ 是包含 $m$ 个 $0$ 或 $1$ 的数组。 请帮助大师计算有多少种方法可以制作一幅美丽的作品。请将答案对 $10^9 + 7$ 取模后输出。

每个测试点包含多组测试用例。第一行包含测试用例的数量 $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$ 种颜色顶点度数之和的奇偶性要求（若和为偶数，则 $\mathrm{mask}_i = 0$，否则 $\mathrm{mask}_i = 1$）。 保证所有测试用例中 $n$ 之和不超过 $10^4$，$m$ 之和也不超过 $10^4$。

对于每个测试用例，输出一个整数，表示制作美丽作品的方案数，对 $10^9 + 7$ 取模。

在第一个测试用例中，一个合法的树结构为边集 $\{(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$，结果为奇数，不符合要求。 由 ChatGPT 5 翻译