A16723. Mosaic Tree
编程题
NOI/NOI+/CTSC
知识点
题目描述
大师制作了一幅由 $n$ 个彩色马赛克元素组成的作品。每个元素被涂成 $m$ 种可能颜色中的一种（颜色编号为 $1$ 到 $m$）。
大师将作品排列成能够表示为一棵树的形式。
如果对于每种颜色 $i$，所有颜色为 $i$ 的顶点的度数之和具有指定的奇偶性 $\mathrm{mask}_i$，则称该作品是美丽的，其中 $\mathrm{mask}$ 是包含 $m$ 个 $0$ 或 $1$ 的数组。
请帮助大师计算有多少种方法可以制作一幅美丽的作品。请将答案对 $10^9 + 7$ 取模后输出。
大师将作品排列成能够表示为一棵树的形式。
如果对于每种颜色 $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$。
每个测试用例的第一行包含两个整数 $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
5 4 2 1 2 1 2 0 0 4 1 1 1 1 1 1 5 1 1 1 1 1 1 0 6 4 1 2 1 2 1 4 0 1 0 1 1 3 3 1 0 0
输出 #1
8 0 125 384 0
说明/提示
在第一个测试用例中，一个合法的树结构为边集 $\{(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$，结果为奇数，不符合要求。
一个非法的树结构为边集 $\{(1, 2), (2, 3), (3, 4)\}$，颜色为 $1$ 的顶点度数总和为 $3$，结果为奇数，不符合要求。