F. Мозаичное дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мастер создает композицию из $$$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$$$ по модулю $$$2$$$, и аналогично, общая степень вершин с цветом $$$2$$$ равна $$$2$$$, что также является $$$0$$$ по модулю $$$2$$$, как требуется в условии.

Пример недопустимого дерева будет описан рёбрами $$$\{(1, 2), (2, 3), (3, 4)\}$$$, так как степени вершин с цветом $$$1$$$ в сумме дают $$$3$$$, что является нечётным числом.