Legenda głosi, że w krainie 夜之国 rośnie tęczowe drzewo o $n$ wierzchołkach. Jest ono drzewem ukorzenionym, którego wierzchołki mają numery od $0$ do $n-1$. Korzeniem jest wierzchołek $0$, a rodzicem wierzchołka $i$ ($1\le i<n$) jest $f_i$.

Każdy wierzchołek tęczowego drzewa może przybrać dowolny kolor. Istnieje nieskończenie wiele kolorów, lecz barwność drzewa zależy wyłącznie od liczby różnych kolorów występujących w każdym poddrzewie, a nie od samych kolorów. Dokładniej, niech w poddrzewie o korzeniu w wierzchołku $i$ ($0\le i<n$) występują wierzchołki w $c_i$ różnych kolorach. Barwność tęczowego drzewa opisujemy ciągiem $[c_0,c_1,\ldots,c_{n-1}]$. Na przykład na poniższym rysunku wierzchołki $0,1,5$ są niebieskie, wierzchołki $2,4$ są czerwone, a wierzchołek $3$ jest żółty, zatem barwność tego drzewa wynosi $[3,2,1,2,1,1]$.

Zmiany w chmurach sprawiają, że kolory tęczowego drzewa podlegają określonej regule. Każdą taką regułę opisuje odpowiadający jej podzbiór wierzchołków $S\subseteq\{1,2,\ldots,n-1\}$: każdy wierzchołek $u$ ze zbioru $S$ ma ten sam kolor co pewien jego przodek. Formalnie, dla każdego $u\in S$ istnieje przodek $p$ wierzchołka $u$ ($p\ne u$), taki że $u$ i $p$ mają ten sam kolor. Mimo tych ograniczeń tęczowe drzewo może przybierać różne kolory, a więc mieć różną barwność. Niech $w_S$ oznacza liczbę różnych barwności tęczowego drzewa spełniającego regułę $S$. Dwie barwności są różne wtedy i tylko wtedy, gdy odpowiadające im ciągi różnią się na co najmniej jednej pozycji.

Oblicz sumę liczb różnych barwności drzew spełniających każdą z $2^{n-1}$ możliwych reguł, czyli $\sum_{S\subseteq\{1,2,\ldots,n-1\}}w_S$. Ponieważ wynik może być duży, podaj jego resztę modulo $998\,244\,353$.

Szczegóły implementacji

Nie musisz i nie powinieneś implementować funkcji main.

Kod źródłowy zgłoszenia musi zawierać nagłówek rainbow.h. W tym celu na początku programu dodaj:

#include "rainbow.h"

W zgłaszanym pliku źródłowym rainbow.cpp zaimplementuj następującą funkcję:

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

• $c,n$ oznaczają odpowiednio numer testu i liczbę wierzchołków tęczowego drzewa. Wartość $c=0$ oznacza test przykładowy.
• $f$ jest ciągiem długości $n$, gdzie $f_0=0$, a $f_i$ ($1\le i<n$) oznacza rodzica wierzchołka $i$.
• Funkcja powinna zwrócić sumę liczb różnych barwności tęczowych drzew spełniających poszczególne reguły, modulo $998\,244\,353$.
• W każdym teście program oceniający wywoła tę funkcję dokładnie raz.

Plik template_rainbow.cpp w katalogu zadania zawiera przykładowy kod, z którego możesz skorzystać przy pisaniu własnego rozwiązania.

Testowanie programu

W katalogu zadania możesz skompilować plik wykonywalny następującym poleceniem:

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

Otrzymany plik wykonywalny rainbow:

• Odczytuje ze standardowego wejścia dane w następującym formacie:

  • Pierwszy wiersz zawiera dwie nieujemne liczby całkowite $c,n$.
  • Drugi wiersz zawiera $n-1$ nieujemnych liczb całkowitych $f_1,f_2,\ldots,f_{n-1}$.

• Wypisuje na standardowe wyjście dane w następującym formacie:

  • Jeden wiersz z jedną nieujemną liczbą całkowitą, oznaczającą wartość zwróconą przez funkcję rainbow.

Przykład

Wejście 1

0 3
0 0

Wyjście 1

8

Uwagi

• Dla reguły $S=\varnothing$ możliwe są trzy barwności tęczowego drzewa: $[1,1,1]$, $[2,1,1]$, $[3,1,1]$.
• Dla reguły $S=\{1\}$ możliwe są dwie barwności: $[1,1,1]$, $[2,1,1]$.
• Dla reguły $S=\{2\}$ możliwe są dwie barwności: $[1,1,1]$, $[2,1,1]$.
• Dla reguły $S=\{1,2\}$ możliwa jest jedna barwność: $[1,1,1]$.

Zatem odpowiedź wynosi $3+2+2+1=8$.

Wejście 2

0 6
0 1 0 3 1

Wyjście 2

279

Przykład 3

Zobacz pliki rainbow/rainbow3.in oraz rainbow/rainbow3.ans w katalogu zawodnika.

Przykład spełnia ograniczenia testów $3,4$.

Przykład 4

Zobacz pliki rainbow/rainbow4.in oraz rainbow/rainbow4.ans w katalogu zawodnika.

Przykład spełnia ograniczenia testów od $5$ do $7$.

Przykład 5

Zobacz pliki rainbow/rainbow5.in oraz rainbow/rainbow5.ans w katalogu zawodnika.

Przykład spełnia ograniczenia testów $8,9$.

Przykład 6

Zobacz pliki rainbow/rainbow6.in oraz rainbow/rainbow6.ans w katalogu zawodnika.

Przykład spełnia ograniczenia testów od $10$ do $12$.

Ograniczenia

Dla wszystkich danych:

• $1\le n\le200$;
• dla każdego $1\le i<n$ zachodzi $0\le f_i<i$.

Szczególna własność A: dla każdego $1\le i<n$ zachodzi $f_i=i-1$.

Szczególna własność B: dla każdego $0\le i<n$ istnieją co najwyżej dwa indeksy $j$, dla których $f_j=i$.