La légende raconte qu'au pays de la Nuit pousse un arbre arc-en-ciel de $n$ sommets. C'est un arbre enraciné dont les sommets sont numérotés de $0$ à $n-1$. Sa racine est le sommet $0$, et le père du sommet $i$, pour $1\le i<n$, est $f_i$.

Chaque sommet peut prendre n'importe quelle couleur, parmi une infinité de couleurs disponibles. Cependant, le profil de diversité de l'arbre ne dépend que du nombre de couleurs distinctes présentes dans chaque sous-arbre, et non des couleurs elles-mêmes. Plus précisément, si le sous-arbre enraciné au sommet $i$, pour $0\le i<n$, contient des sommets de $c_i$ couleurs distinctes, ce profil est la séquence $[c_0,c_1,\ldots,c_{n-1}]$. Dans la figure suivante, les sommets $0,1,5$ sont bleus, les sommets $2,4$ rouges et le sommet $3$ jaune ; le profil de diversité est donc $[3,2,1,2,1,1]$.

Les changements dans les nuages imposent une certaine règle aux couleurs de l'arbre. Chaque règle est décrite par un sous-ensemble $S\subseteq\{1,2,\ldots,n-1\}$ : tout sommet $u$ de $S$ doit avoir la même couleur qu'un de ses ancêtres. Formellement, pour tout $u\in S$, il existe un ancêtre $p$ de $u$, avec $p\ne u$, de la même couleur que $u$. Malgré cette règle, différentes colorations peuvent produire différents profils de diversité. Notons $w_S$ le nombre de profils de diversité distincts des arbres arc-en-ciel respectant la règle $S$. Deux profils sont distincts si et seulement si leurs séquences diffèrent sur au moins un élément.

Calculez la somme de ces nombres pour les $2^{n-1}$ règles possibles, soit

$$ \sum_{S\subseteq\{1,2,\ldots,n-1\}}w_S. $$

La réponse pouvant être grande, affichez seulement son reste modulo $998\,244\,353$.

Détails d'implémentation

Vous ne devez pas implémenter de fonction main.

Le fichier source soumis doit inclure l'en-tête rainbow.h. Ajoutez donc au début :

#include "rainbow.h"

Dans le fichier source rainbow.cpp soumis, implémentez la fonction suivante :

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

• $c,n$ sont respectivement le numéro du test et le nombre de sommets de l'arbre. La valeur $c=0$ indique un exemple.
• $f$ est une séquence de longueur $n$, où $f_0=0$ et où $f_i$, pour $1\le i<n$, est le père du sommet $i$.
• La fonction doit renvoyer la somme des nombres de profils de diversité respectant chaque règle, modulo $998\,244\,353$.
• Pour chaque test, l'évaluateur appelle cette fonction exactement une fois.

Le fichier template_rainbow.cpp fourni dans le répertoire du problème contient un exemple de code que vous pouvez utiliser comme référence pour votre implémentation.

Test de votre programme

Dans le répertoire du problème, vous pouvez compiler un exécutable avec :

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

Pour l'exécutable rainbow ainsi compilé :

• Il lit les données suivantes sur l'entrée standard :

  • La première ligne contient deux entiers positifs ou nuls $c,n$.
  • La deuxième ligne contient $n-1$ entiers positifs ou nuls $f_1,f_2,\ldots,f_{n-1}$.

• Il écrit sur la sortie standard :

  • Une ligne contenant un entier positif ou nul, la valeur renvoyée par rainbow.

Exemples

Entrée 1

0 3
0 0

Sortie 1

8

Remarque

• Pour $S=\varnothing$, les trois profils possibles sont $[1,1,1]$, $[2,1,1]$ et $[3,1,1]$.
• Pour $S=\{1\}$, les deux profils possibles sont $[1,1,1]$ et $[2,1,1]$.
• Pour $S=\{2\}$, les deux profils possibles sont $[1,1,1]$ et $[2,1,1]$.
• Pour $S=\{1,2\}$, le seul profil possible est $[1,1,1]$.

La réponse est donc $3+2+2+1=8$.

Entrée 2

0 6
0 1 0 3 1

Sortie 2

279

Exemple 3

Voir rainbow/rainbow3.in et rainbow/rainbow3.ans dans le répertoire des candidats.

Cet exemple respecte les contraintes des tests $3,4$.

Exemple 4

Voir rainbow/rainbow4.in et rainbow/rainbow4.ans dans le répertoire des candidats.

Cet exemple respecte les contraintes des tests $5\sim7$.

Exemple 5

Voir rainbow/rainbow5.in et rainbow/rainbow5.ans dans le répertoire des candidats.

Cet exemple respecte les contraintes des tests $8,9$.

Exemple 6

Voir rainbow/rainbow6.in et rainbow/rainbow6.ans dans le répertoire des candidats.

Cet exemple respecte les contraintes des tests $10\sim12$.

Contraintes

Pour toutes les données :

• $1\le n\le200$ ;
• Pour tout $1\le i<n$, $0\le f_i<i$.

Propriété particulière A : pour tout $1\le i<n$, $f_i=i-1$.

Propriété particulière B : pour tout $0\le i<n$, il existe au plus deux indices $j$ tels que $f_j=i$.