大师创作了 $$$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$$$ 为模。
示例
输入复制
54 21 2 1 20 04 11 1 1 115 11 1 1 1 106 41 2 1 2 1 40 1 0 11 331 0 0
输出复制
801253840
注意
在第一个测试用例中,树的有效示例将由边 $$$\{(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$$$ 相加,这是奇数。