E. Квантификатор
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дано корневое дерево с $$$n+1$$$ вершинами, пронумерованными от $$$0$$$ до $$$n$$$, где корень — это вершина $$$0$$$, а его единственный ребенок — вершина $$$1$$$. Есть $$$m$$$ различных фишек, помеченных от $$$1$$$ до $$$m$$$, каждая из которых окрашена либо в черный, либо в белый цвет. Изначально они расположены на ребре $$$(0,1)$$$ сверху вниз в порядке возрастания номеров.

Начальное положение фишек. Вершины дерева показаны синим.

Вы можете выполнять следующие операции любое количество раз (возможно, ноль) в любом порядке:

  • Выберите два ребра ($$$u,v$$$) и ($$$v,w$$$), такие что $$$u$$$ является родителем $$$v$$$, а $$$v$$$ является родителем $$$w$$$, где ребро ($$$u,v$$$) содержит хотя бы одну фишку. Переместите самую нижнюю фишку на ребре ($$$u,v$$$) в самый верх ребра ($$$v,w$$$), т.е. над всеми существующими фишками на ($$$v,w$$$).
  • Выберите два ребра ($$$u,v$$$) и ($$$v,w$$$), такие что $$$u$$$ является родителем $$$v$$$, а $$$v$$$ является родителем $$$w$$$, где ребро ($$$v,w$$$) содержит хотя бы одну фишку. Переместите самую верхнюю фишку на ребре ($$$v,w$$$) в самый низ ребра ($$$u,v$$$), т.е. под все фишки на ($$$u,v$$$).
  • Выберите две соседние фишки одного цвета на одном ребре и поменяйте их местами.
Разрешенные операции.

Каждая фишка $$$i$$$ имеет диапазон движения, определяемый всеми ребрами на простом пути от корня до вершины $$$d_i$$$. Во время операций вы должны гарантировать, что ни одна фишка не перемещается на ребро вне своего диапазона движения.

В итоге вы должны вернуть все фишки обратно на ребро $$$(0,1)$$$. Порядок фишек может измениться. Вычислите количество достижимых перестановок фишек на ребре $$$(0,1)$$$ по модулю $$$998\,244\,353$$$.

Перестановка фишек определяется как последовательность длины $$$m$$$, состоящая из номеров фишек в порядке сверху вниз.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 5000$$$) — размер дерева минус один (т. е. дерево имеет $$$n+1$$$ вершину) и количество фишек.

Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i \lt i$$$) — родительские вершины для вершин от $$$1$$$ до $$$n$$$. Гарантируется, что $$$p_i = 0$$$ тогда и только тогда, когда $$$i = 1$$$ (единственный ребенок корня — вершина $$$1$$$).

Третья строка содержит $$$m$$$ целых чисел $$$c_1, c_2, \ldots, c_m$$$ ($$$c_i \in \{0, 1\}$$$) — цвет каждой фишки ($$$0$$$ для черного, $$$1$$$ для белого).

Четвертая строка содержит $$$m$$$ целых чисел $$$d_1, d_2, \ldots, d_m$$$ ($$$1\le d_i \le n$$$) — диапазон движения каждой фишки.

Гарантируется, что сумма $$$n$$$ не превышает $$$5000$$$, а сумма $$$m$$$ не превышает $$$5000$$$ по всем наборам входных данных.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество возможных перестановок по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4
3 2
0 1 1
0 1
2 3
4 4
0 1 1 2
0 0 1 1
1 2 3 3
6 6
0 1 1 1 4 5
0 0 0 0 1 1
5 6 1 2 4 3
16 15
0 1 1 3 1 3 4 3 3 7 1 6 11 5 8 10
1 0 1 1 0 1 1 1 1 0 1 1 0 0 0
12 14 13 10 9 16 11 14 13 15 16 10 2 2 5
Выходные данные
2
8
108
328459046
Примечание

В первом наборе входных данных можно получить следующие $$$2$$$ перестановки: ($$$1,2$$$) и ($$$2,1$$$).

Во втором наборе входных данных можно получить следующие $$$8$$$ перестановок: ($$$1,2,3,4$$$), ($$$1,2,4,3$$$), ($$$1,3,2,4$$$), ($$$1,3,4,2$$$), ($$$1,4,2,3$$$), ($$$1,4,3,2$$$), ($$$2,1,3,4$$$) и ($$$2,1,4,3$$$).