H. Обрезание дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево с $$$n$$$ вершинами.

Герой $$$k$$$ раз делает следующую операцию:

  • Выбрать некоторое ребро.
  • Удалить его.
  • Выбрать одну из двух оставшихся частей и удалить ее.
  • Записать количество вершин в оставшейся части.

Вам дано изначальное дерево и последовательность выписанных чисел. Найдите количество способов сделать операции так, что выписанные числа совпадут с данными числами. Поскольку ответ может быть очень большим, найдите его по модулю $$$998\,244\,353$$$. Два способа считаются различными, если в какой-то операции выбранное ребро или остающаяся часть различаются.

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

В первой строке находится единственное целое число $$$n$$$ ($$$2 \leq n \leq 5000$$$) — количество вершин.

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$s$$$, $$$f$$$ ($$$1 \leq s, f \leq n$$$, $$$s \neq f$$$) — описание ребра $$$(s, f)$$$.

Следующая строка содержит единственное целое число $$$k$$$ ($$$1 \leq k \leq \min{(6, n - 1)}$$$) — количество операций.

В следующей строке находится $$$k$$$ целых чисел $$$s_1, s_2, \ldots, s_k$$$ ($$$n > s_1 > s_2 > \ldots > s_k \geq 1$$$) — выписанные числа.

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

Выведите единственное целое число — ответы на задачу по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
3
1 2
2 3
2
2 1
Выходные данные
4
Входные данные
7
2 1
3 2
4 1
5 3
6 4
7 4
2
4 2
Выходные данные
2
Входные данные
7
1 2
1 3
1 4
2 5
3 6
4 7
1
2
Выходные данные
3
Входные данные
7
1 2
1 3
1 4
2 5
3 6
4 7
4
6 5 2 1
Выходные данные
24
Входные данные
8
1 2
2 3
3 4
3 5
3 6
3 7
3 8
2
7 4
Выходные данные
0
Примечание

В первом тесте есть четыре возможных способа сделать операции:

  • Удалить ребро $$$(1, 2)$$$ и удалить вершину $$$1$$$. Удалить ребро $$$(2, 3)$$$ и удалить вершину $$$2$$$.
  • Удалить ребро $$$(1, 2)$$$ и удалить вершину $$$1$$$. Удалить ребро $$$(3, 2)$$$ и удалить вершину $$$3$$$.
  • Удалить ребро $$$(3, 2)$$$ и удалить вершину $$$3$$$. Удалить ребро $$$(1, 2)$$$ и удалить вершину $$$1$$$.
  • Удалить ребро $$$(3, 2)$$$ и удалить вершину $$$3$$$. Удалить ребро $$$(2, 1)$$$ и удалить вершину $$$2$$$.

Во втором тесте есть два возможных способа сделать операции:

  • Удалить ребро $$$(4, 1)$$$ и удалить часть с вершиной $$$4$$$. Удалить ребро $$$(2, 3)$$$ и удалить часть с вершиной $$$2$$$.
  • Удалить ребро $$$(4, 1)$$$ и удалить часть с вершиной $$$4$$$. Удалить ребро $$$(3, 2)$$$ и удалить часть с вершиной $$$3$$$.