Согласно легенде, в Стране ночи растёт радужное дерево с $n$ вершинами. Это корневое дерево с вершинами, пронумерованными от $0$ до $n-1$. Его корень — вершина $0$, а родитель вершины $i$ ($1\le i<n$) — вершина $f_i$.

Каждая вершина радужного дерева может принимать любой цвет. Цветов бесконечно много, но пестрота дерева зависит только от количества различных цветов в каждом поддереве, а не от самих цветов. А именно, пусть в поддереве с корнем $i$ ($0\le i<n$) встречаются $c_i$ различных цветов. Тогда пестрота дерева задаётся последовательностью $[c_0,c_1,\ldots,c_{n-1}]$. Например, на рисунке ниже вершины $0,1,5$ синие, вершины $2,4$ красные, а вершина $3$ жёлтая; поэтому пестрота дерева равна $[3,2,1,2,1,1]$.

Изменения облаков заставляют цвета радужного дерева подчиняться определённым закономерностям. Каждая закономерность описывается подмножеством вершин $S\subseteq\{1,2,\ldots,n-1\}$: цвет каждой вершины $u$ из $S$ совпадает с цветом некоторого её предка. Формально, для любого $u\in S$ существует предок $p$ вершины $u$ ($p\ne u$), имеющий тот же цвет, что и $u$. Даже при соблюдении закономерности дерево может иметь разные раскраски и разную пестроту. Обозначим через $w_S$ количество различных вариантов пестроты дерева, удовлетворяющих закономерности $S$. Два варианта пестроты различны тогда и только тогда, когда соответствующие последовательности различаются хотя бы в одном элементе.

Вычислите сумму количеств вариантов пестроты для всех $2^{n-1}$ возможных закономерностей, то есть $\sum_{S\subseteq\{1,2,\ldots,n-1\}}w_S$. Поскольку ответ может быть большим, выведите его по модулю $998244353$.

Детали реализации

Не нужно и не следует реализовывать функцию main.

Отправляемый исходный файл должен подключать заголовок rainbow.h. Добавьте в начало программы:

#include "rainbow.h"

В отправляемом исходном файле rainbow.cpp нужно реализовать функцию:

int rainbow(int c, int n, std::vector<int> f);

• $c,n$ — соответственно номер теста и количество вершин радужного дерева. Значение $c=0$ означает пример.
• $f$ — последовательность длины $n$, где $f_0=0$, а $f_i$ ($1\le i<n$) — родитель вершины $i$.
• Функция должна вернуть сумму количеств вариантов пестроты радужного дерева, удовлетворяющих каждой закономерности, по модулю $998244353$.
• В каждом тесте проверяющая программа вызовет эту функцию ровно один раз.

В каталоге задачи предоставлен пример кода template_rainbow.cpp. Можно использовать его при написании своего решения.

Проверка программы

В каталоге задачи можно скомпилировать исполняемый файл следующей командой:

g++ grader.cpp rainbow.cpp -o rainbow -O2 -std=c++14 -static

Полученный исполняемый файл rainbow работает следующим образом.

Он считывает со стандартного ввода данные следующего формата:

• Первая строка содержит два неотрицательных целых числа $c,n$.
• Вторая строка содержит $n-1$ неотрицательных целых чисел $f_1,f_2,\ldots,f_{n-1}$.

Он выводит в стандартный вывод данные следующего формата:

• Одна строка с одним неотрицательным целым числом — результатом функции rainbow.

Примеры

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

0 3
0 0

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

8

Примечание

• Закономерности $S=\varnothing$ удовлетворяют три варианта пестроты: $[1,1,1]$, $[2,1,1]$, $[3,1,1]$.
• Закономерности $S=\{1\}$ удовлетворяют два варианта пестроты: $[1,1,1]$, $[2,1,1]$.
• Закономерности $S=\{2\}$ удовлетворяют два варианта пестроты: $[1,1,1]$, $[2,1,1]$.
• Закономерности $S=\{1,2\}$ удовлетворяет один вариант пестроты: $[1,1,1]$.

Поэтому ответ равен $3+2+2+1=8$.

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

0 6
0 1 0 3 1

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

279

Пример 3

См. файлы rainbow/rainbow3.in и rainbow/rainbow3.ans в каталоге участника.

Этот пример удовлетворяет ограничениям тестов $3,4$.

Пример 4

См. файлы rainbow/rainbow4.in и rainbow/rainbow4.ans в каталоге участника.

Этот пример удовлетворяет ограничениям тестов $5\sim7$.

Пример 5

См. файлы rainbow/rainbow5.in и rainbow/rainbow5.ans в каталоге участника.

Этот пример удовлетворяет ограничениям тестов $8,9$.

Пример 6

См. файлы rainbow/rainbow6.in и rainbow/rainbow6.ans в каталоге участника.

Этот пример удовлетворяет ограничениям тестов $10\sim12$.

Ограничения

Для всех тестовых данных выполняются условия:

• $1\le n\le200$;
• Для любого $1\le i<n$ выполняется $0\le f_i<i$.

Особое свойство A: для любого $1\le i<n$ выполняется $f_i=i-1$.

Особое свойство B: для любого $0\le i<n$ существует не более двух значений $j$, удовлетворяющих $f_j=i$.