Cuenta la leyenda que en el Reino de la Noche hay un árbol arcoíris de $n$ nodos. Es un árbol enraizado cuyos nodos se numeran de $0$ a $n-1$. Su raíz es el nodo $0$, y el padre del nodo $i$ ($1\le i<n$) es $f_i$.

Cada nodo puede adoptar cualquier color. Hay infinitos colores, pero la variedad cromática del árbol depende únicamente del número de colores distintos que aparecen en cada subárbol, y no de cuáles sean esos colores. En concreto, si el subárbol con raíz en $i$ ($0\le i<n$) contiene nodos de $c_i$ colores distintos, la variedad cromática del árbol se representa mediante la secuencia $[c_0,c_1,\ldots,c_{n-1}]$. Por ejemplo, en la figura siguiente, los nodos $0,1,5$ son azules, los nodos $2,4$ son rojos y el nodo $3$ es amarillo. La variedad cromática es, por tanto, $[3,2,1,2,1,1]$.

Los cambios en las nubes hacen que los colores del árbol sigan determinadas reglas. Cada regla se describe mediante un subconjunto de nodos $S\subseteq\{1,2,\ldots,n-1\}$: cada nodo $u$ de $S$ tiene el mismo color que alguno de sus ancestros. Formalmente, para todo $u\in S$ existe un ancestro $p$ de $u$, con $p\ne u$, tal que $u$ y $p$ tienen el mismo color. A pesar de esta restricción, el árbol puede mostrar distintas coloraciones y, con ellas, distintas variedades cromáticas. Sea $w_S$ el número de variedades cromáticas posibles que cumplen la regla $S$. Dos variedades cromáticas son distintas si y solo si las dos secuencias difieren en al menos un elemento.

Calcula la suma de esos números de variedades cromáticas para las $2^{n-1}$ reglas posibles, es decir, $\sum_{S\subseteq\{1,2,\ldots,n-1\}}w_S$. Como la respuesta puede ser grande, solo tienes que dar su valor módulo $998\,244\,353$.

Detalles de implementación

No necesitas ni debes implementar la función main.

Asegúrate de incluir la cabecera rainbow.h al principio del código fuente que envíes:

#include "rainbow.h"

Debes implementar la siguiente función en el archivo rainbow.cpp:

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

• $c,n$ indican, respectivamente, el número del punto de prueba y el número de nodos del árbol arcoíris. $c=0$ indica que se trata de un ejemplo.
• $f$ es una secuencia de longitud $n$, con $f_0=0$ y $f_i$ ($1\le i<n$) igual al padre del nodo $i$.
• La función debe devolver la suma de los números de variedades cromáticas del árbol que cumplen cada regla, módulo $998\,244\,353$.
• El evaluador llamará a esta función exactamente una vez por punto de prueba.

El archivo template_rainbow.cpp del directorio del problema contiene el código de ejemplo proporcionado, que puedes consultar para escribir tu implementación.

Cómo probar el programa

Puedes compilar un ejecutable con el siguiente comando en el directorio del problema:

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

Para el ejecutable rainbow obtenido:

• Lee de la entrada estándar datos con el siguiente formato:

  • La primera línea contiene dos enteros no negativos $c,n$.
  • La segunda contiene $n-1$ enteros no negativos $f_1,f_2,\ldots,f_{n-1}$.

• Escribe en la salida estándar datos con el siguiente formato:

  • Una línea con un entero no negativo: el valor devuelto por la función rainbow.

Ejemplos

Entrada 1

0 3
0 0

Salida 1

8

Nota

• Para la regla $S=\varnothing$, hay tres variedades cromáticas: $[1,1,1]$, $[2,1,1]$, $[3,1,1]$.
• Para la regla $S=\{1\}$, hay dos: $[1,1,1]$, $[2,1,1]$.
• Para la regla $S=\{2\}$, hay dos: $[1,1,1]$, $[2,1,1]$.
• Para la regla $S=\{1,2\}$, hay una: $[1,1,1]$.

Por tanto, la respuesta es $3+2+2+1=8$.

Entrada 2

0 6
0 1 0 3 1

Salida 2

279

Ejemplo 3

Consulta rainbow/rainbow3.in y rainbow/rainbow3.ans en el directorio del concursante.

Este ejemplo cumple las restricciones de los puntos de prueba $3,4$.

Ejemplo 4

Consulta rainbow/rainbow4.in y rainbow/rainbow4.ans en el directorio del concursante.

Este ejemplo cumple las restricciones de los puntos de prueba $5\sim7$.

Ejemplo 5

Consulta rainbow/rainbow5.in y rainbow/rainbow5.ans en el directorio del concursante.

Este ejemplo cumple las restricciones de los puntos de prueba $8,9$.

Ejemplo 6

Consulta rainbow/rainbow6.in y rainbow/rainbow6.ans en el directorio del concursante.

Este ejemplo cumple las restricciones de los puntos de prueba $10\sim12$.

Restricciones

Para todos los datos de prueba:

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

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

Propiedad especial B: para todo $0\le i<n$, hay como máximo dos valores de $j$ que satisfacen $f_j=i$.