За легендою, у Країні ночі є веселкове дерево з $n$ вершинами. Веселкове дерево — кореневе дерево, вершини якого пронумеровані $0\sim 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$ та $p$ мають однаковий колір. Незважаючи на ці обмеження, дерево може набувати різних кольорів і утворювати різні барвистості. Позначимо через $w_S$ кількість різних барвистостей дерева, що задовольняє закономірність $S$. Дві барвистості різні тоді й лише тоді, коли відповідні послідовності відрізняються хоча б одним елементом.

Обчисліть суму кількостей різних барвистостей дерева, що задовольняє кожну з усіх можливих $2^{n-1}$ закономірностей, тобто $\sum_{S\subseteq\{1,2,\ldots,n-1\}}w_S$. Оскільки відповідь може бути великою, достатньо знайти її остачу від ділення на $998\,244\,353$.

Деталі реалізації

Ви не повинні й не маєте потреби реалізовувати функцію 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$.
• Функція має повернути остачу від ділення на $998\,244\,353$ суми кількостей різних барвистостей веселкового дерева, що задовольняє кожну закономірність.
• Для кожного тесту перевіряльна програма викличе цю функцію рівно один раз.

Файл 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

Пояснення до прикладу 1

• Для закономірності $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$.