Вам дано дерево с \(n\) вершинами.
Герой \(k\) раз делает следующую операцию:
- Выбрать некоторое ребро.
- Удалить его.
- Выбрать одну из двух оставшихся частей и удалить ее.
- Записать количество вершин в оставшейся части.
Вам дано изначальное дерево и последовательность выписанных чисел. Найдите количество способов сделать операции так, что выписанные числа совпадут с данными числами. Поскольку ответ может быть очень большим, найдите его по модулю \(998\,244\,353\). Два способа считаются различными, если в какой-то операции выбранное ребро или остающаяся часть различаются.
Выходные данные
Выведите единственное целое число — ответы на задачу по модулю \(998\,244\,353\).
Примечание
В первом тесте есть четыре возможных способа сделать операции:
- Удалить ребро \((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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
2 3
2
2 1
|
4
|
|
2
|
7
2 1
3 2
4 1
5 3
6 4
7 4
2
4 2
|
2
|
|
3
|
7
1 2
1 3
1 4
2 5
3 6
4 7
1
2
|
3
|
|
4
|
7
1 2
1 3
1 4
2 5
3 6
4 7
4
6 5 2 1
|
24
|
|
5
|
8
1 2
2 3
3 4
3 5
3 6
3 7
3 8
2
7 4
|
0
|