Вам дано дерево с $$$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
В первом тесте есть четыре возможных способа сделать операции:
Во втором тесте есть два возможных способа сделать операции:
Название |
---|