Conta-se que, no País da Noite, há uma árvore arco-íris com $n$ vértices. Ela é uma árvore enraizada cujos vértices são numerados de $0$ a $n-1$. O vértice $0$ é a raiz, e o pai do vértice $i$ ($1\le i<n$) é $f_i$.

Cada vértice da árvore arco-íris pode exibir qualquer cor. Há infinitas cores, mas a diversidade cromática da árvore depende apenas do número de cores distintas presentes em cada subárvore, sem depender das cores específicas. Mais precisamente, se a subárvore enraizada no vértice $i$ ($0\le i<n$) contém vértices de $c_i$ cores distintas, a diversidade cromática da árvore é representada pela sequência $[c_0,c_1,\ldots,c_{n-1}]$. Por exemplo, na figura abaixo, os vértices $0,1,5$ são azuis, os vértices $2,4$ são vermelhos e o vértice $3$ é amarelo. Assim, a diversidade cromática da árvore é $[3,2,1,2,1,1]$.

Mudanças nas nuvens fazem as cores da árvore arco-íris obedecerem a determinados padrões. Cada padrão é descrito por um subconjunto de vértices $S\subseteq\{1,2,\ldots,n-1\}$: cada vértice $u$ de $S$ tem a mesma cor de algum ancestral. Formalmente, para todo $u\in S$, existe um ancestral $p$ de $u$, com $p\ne u$, tal que $u$ e $p$ têm a mesma cor. Mesmo sob essa restrição, a árvore pode apresentar diferentes colorações e, portanto, diferentes diversidades cromáticas. Seja $w_S$ o número de diversidades cromáticas distintas das árvores arco-íris que satisfazem o padrão $S$. Duas diversidades cromáticas são distintas se, e somente se, suas sequências diferem em pelo menos um elemento.

Calcule a soma dos números de diversidades cromáticas para todos os $2^{n-1}$ padrões possíveis, isto é, $\sum_{S\subseteq\{1,2,\ldots,n-1\}}w_S$. Como a resposta pode ser grande, calcule apenas o resultado módulo $998\,244\,353$.

Detalhes de implementação

Você não precisa e não deve implementar a função main.

O código-fonte submetido deve incluir o cabeçalho rainbow.h; portanto, adicione a seguinte linha no início do programa:

#include "rainbow.h"

Você deve implementar a seguinte função no arquivo-fonte submetido rainbow.cpp:

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

• $c,n$ representam, respectivamente, o número do caso de teste e o número de vértices da árvore arco-íris. $c=0$ indica um exemplo.
• $f$ é uma sequência de comprimento $n$, na qual $f_0=0$ e $f_i$ ($1\le i<n$) é o pai do vértice $i$.
• A função deve retornar a soma dos números de diversidades cromáticas das árvores que satisfazem cada padrão, módulo $998\,244\,353$.
• Para cada caso de teste, a função será chamada pelo programa de avaliação exatamente uma vez.

O arquivo template_rainbow.cpp no diretório deste problema contém o código de exemplo fornecido. Você pode usá-lo como referência para sua implementação.

Como testar o programa

Você pode compilar um executável no diretório deste problema com o seguinte comando:

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

Para o executável compilado rainbow:

• Ele lê da entrada padrão dados no seguinte formato:

  • A primeira linha contém dois inteiros não negativos $c,n$.
  • A segunda linha contém $n-1$ inteiros não negativos $f_1,f_2,\ldots,f_{n-1}$.

• Ele escreve na saída padrão dados no seguinte formato:

  • Uma linha com um inteiro não negativo: o valor retornado pela função rainbow.

Exemplos

Entrada 1

0 3
0 0

Saída 1

8

Nota

• Para o padrão $S=\varnothing$, há três diversidades cromáticas: $[1,1,1]$, $[2,1,1]$, $[3,1,1]$;
• Para o padrão $S=\{1\}$, há duas diversidades cromáticas: $[1,1,1]$, $[2,1,1]$;
• Para o padrão $S=\{2\}$, há duas diversidades cromáticas: $[1,1,1]$, $[2,1,1]$;
• Para o padrão $S=\{1,2\}$, há uma diversidade cromática: $[1,1,1]$.

Portanto, a resposta é $3+2+2+1=8$.

Entrada 2

0 6
0 1 0 3 1

Saída 2

279

Exemplo 3

Veja rainbow/rainbow3.in e rainbow/rainbow3.ans no diretório dos competidores.

Esse exemplo satisfaz as restrições dos casos de teste $3,4$.

Exemplo 4

Veja rainbow/rainbow4.in e rainbow/rainbow4.ans no diretório dos competidores.

Esse exemplo satisfaz as restrições dos casos de teste $5\sim7$.

Exemplo 5

Veja rainbow/rainbow5.in e rainbow/rainbow5.ans no diretório dos competidores.

Esse exemplo satisfaz as restrições dos casos de teste $8,9$.

Exemplo 6

Veja rainbow/rainbow6.in e rainbow/rainbow6.ans no diretório dos competidores.

Esse exemplo satisfaz as restrições dos casos de teste $10\sim12$.

Restrições

Para todos os dados de teste:

• $1\le n\le200$;
• Para todo $1\le i<n$, $0\le f_i<i$.

Propriedade especial A: para todo $1\le i<n$, $f_i=i-1$.

Propriedade especial B: para todo $0\le i<n$, existem no máximo dois valores de $j$ tais que $f_j=i$.