← 返回题目列表

Codeforces · 2174/F

F. 马赛克树

中文机器翻译题面 查看原题

大师创作了 $$$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$$$ 的奇偶性(如果颜色 $$$i$$$ 的顶点总度数应该是偶数, $$$\mathrm{mask}_i = 0$$$,否则 — $$$\mathrm{mask}_i = 1$$$)。

保证所有测试用例的$$$n$$$的值之和不超过$$$10^4$$$,并且还保证所有测试用例的$$$m$$$的值之和不超过$$$10^4$$$。

输出

对于每个测试用例,在单独的行上输出一个整数 - 创建漂亮构图的方法数以 $$$10^9 + 7$$$ 为模。

示例

输入
复制

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

输出
复制

8
0
125
384
0

注意

在第一个测试用例中,树的有效示例将由边 $$$\{(1, 2), (1, 3), (1, 4)\}$$$ 描述。这里,度数分别为 $$$3, 1, 1, 1$$$。这里,颜色为$$$1$$$的顶点的总度数为$$$4$$$,即$$$0$$$ mod $$$2$$$,同样,颜色为$$$2$$$的顶点的总度数为$$$2$$$,这也是$$$0$$$ mod $$$2$$$,根据语句的要求。

无效树的示例可以通过边 $$$\{(1, 2), (2, 3), (3, 4)\}$$$ 来描述,因为颜色为 $$$1$$$ 的顶点的度数与 $$$3$$$ 相加,这是奇数。