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

У Джокера есть дерево, в котором он выбрал $$$m$$$ простых путей: $$$(u_1, v_1)$$$, $$$(u_2, v_2)$$$, $$$\ldots$$$, $$$(u_m, v_m)$$$ — каждый путь задается двумя вершинами $$$u_i$$$ и $$$v_i$$$, лежащими на его концах. Причем все пути имеют ненулевую длину, то есть $$$u_i \neq v_i$$$.

Теперь Джокер хочет расставить на ребрах дерева веса — целые числа $$$0$$$ или $$$1$$$. Обозначим $$$s_i$$$ сумму весов ребер на $$$i$$$-м пути по модулю $$$2$$$ (иначе говоря, исключающее ИЛИ весов всех ребер на этом пути). Джокер называет расстановку весов на ребрах безумной, если выполняется неравенство $$$s_{i} \le s_{i+1}$$$ для всех $$$1 \le i \lt m$$$.

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

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

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — количество вершин в дереве и количество выбранных путей ($$$2 \le n, m \le 250\,000$$$).

Во второй строке дано $$$n - 1$$$ целое число $$$p_i$$$, обозначающее, что в дереве есть ребро между вершинами с номерами $$$p_i$$$ и $$$i + 1$$$ ($$$1 \le p_i \lt i + 1$$$).

В следующих $$$m$$$ строках дано по два целых числа $$$u_i$$$ и $$$v_i$$$ — концы $$$i$$$-го пути ($$$1 \leq u_i \lt v_i \leq n$$$).

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

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

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