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

У Васи есть дерево с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$, и $$$n - 1$$$ рёбрами, пронумерованными от $$$1$$$ до $$$n - 1$$$. Исходно в каждой вершине находится жетон, на котором написан номер вершины.

Вася играет в игру. Он рассматривает все рёбра в порядке возрастания номеров. Для каждого ребра он делает следующее:

  • Если в каждом из концов ребра находится по жетону, удалить один из жетонов и записать его номер.
  • Иначе, ничего не делать.

Результатом игры является последовательность чисел, которую выписал Вася. Последовательности могут получаться различными в зависимости от того, из каких концов рёбер Вася берёт жетоны.

Вася играл очень долго и считает, что выписал все возможные различные последовательности, которые могли получиться. Он просит вас проверить его и посчитать количество различных итоговых последовательностей по модулю $$$998\,244\,353$$$.

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

В первой строке записано одно целое число $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — количество вершин дерева.

Следующие $$$n - 1$$$ строк описывают рёбра дерева. В $$$i$$$-ё из этих строк записано два целых числа $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — концы рёбра с номером $$$i$$$. Гарантируется, что описанный граф является деревом.

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

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

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

В первом примере различные последовательности таковы: $$$(1), (2, 1), (2, 3, 1), (2, 3, 4, 1), (2, 3, 4, 5)$$$.

Во втором примере различные последовательности таковы: $$$(2, 6, 5, 3), (2, 6, 5, 7), (2, 6, 7, 2), (2, 6, 7, 5), (2, 7, 3), (2, 7, 5), (7, 1, 3), (7, 1, 5), (7, 2, 3), (7, 2, 5)$$$.