Jiulian est une jeune fille qui aime créer des problèmes.

Après la World Final de cette année, elle se passionne pour la géométrie algorithmique et décide d'en proposer un problème au NOI : en réalité, seul le nom du problème a un rapport avec la géométrie algorithmique.

Elle donne d'abord un arbre enraciné $T$ à $n$ sommets, avec $n\ge2$, dont la racine porte le numéro $1$. Les feuilles sont tous les sommets autres que la racine ayant un degré exactement égal à $1$. Dans l'exemple suivant, l'ensemble des feuilles est $\{3,4,5\}$.

Jiulian construit ensuite une séquence $A$ à partir de cet arbre :

• Elle effectue un parcours en profondeur de l'arbre depuis la racine, en visitant les enfants dans l'ordre croissant de leurs numéros. Elle obtient ainsi un ordre DFS de $T$.
• Elle range ensuite les feuilles dans l'ordre de leur apparition dans cet ordre DFS, de la première à la dernière, pour former la séquence $A$.

À partir de $A$, elle définit la distance $d(u,v)$ de deux feuilles $u,v$ : si $u$ est l'élément en position $i$ et $v$ celui en position $j$ dans $A$, alors $d(u,v)=\min(|i-j|,|A|-|i-j|)$. Ici, $|A|$ est la longueur de la séquence, donc le nombre de feuilles de $T$, et les positions $i,j$ sont comptées à partir de $1$.

Dans l'exemple précédent, $A=[4,5,3]$, $d(3,5)=d(3,4)=d(4,5)=1$, et les positions de $3,4,5$ sont respectivement $3,1,2$.

Enfin, Jiulian donne un paramètre $K$. À partir de $T$ et de $A$, on construit un graphe non orienté $G$ à $n$ sommets, sans arêtes multiples ni boucles : deux sommets distincts $u,v$ sont reliés si et seulement si au moins une des conditions suivantes est satisfaite :

• Une arête de $T$ relie $u$ et $v$.
• $u$ et $v$ sont tous deux des feuilles de $T$ et $d(u,v)\le K$.

Pour $K=1$ ou $K=2$, l'exemple précédent donne dans les deux cas le graphe $G$ représenté ci-dessous.

Jiulian vous demande de calculer le nombre de cycles hamiltoniens distincts de $G$. La réponse pouvant être grande, affichez-la modulo $998244353$.

Voici quelques définitions supplémentaires :

• Un cycle hamiltonien $H$ d'un graphe non orienté $G$ sans arêtes multiples ni boucles est un sous-ensemble de ses arêtes tel que chaque sommet possède exactement deux arêtes incidentes distinctes dans $H$, et que deux sommets quelconques puissent être reliés, directement ou indirectement, par les arêtes de $H$.
• Deux cycles hamiltoniens $H_1,H_2$ de $G$ sont distincts si et seulement s'il existe une arête $e$ appartenant à $H_1$ et n'appartenant pas à $H_2$.

Entrée

Les données sont lues dans le fichier polygon.in.

La première ligne contient deux entiers $n,K$, le nombre de sommets de $T$ et le paramètre choisi par Jiulian.

La deuxième contient $n-1$ entiers $f_i$, avec $1\le f_i\le i$, indiquant qu'il existe une arête $(f_i,i+1)$ dans $T$.

Sortie

Écrivez la sortie dans le fichier polygon.out.

Affichez sur une ligne un entier : le nombre de cycles hamiltoniens modulo $998244353$.

Exemples

Entrée 1

5 1
1 1 2 2

Sortie 1

2

Remarque

Cet exemple est exactement celui de l'énoncé. Les deux cycles hamiltoniens visitent les sommets dans les ordres $(1,2,4,5,3)$ et $(1,2,5,4,3)$.

Sous-tâches

Les tailles et les propriétés des données de chaque test sont les suivantes :

La propriété A garantit que chaque sommet de l'arbre a au plus deux enfants.

Pour toutes les données, $1\le f_i\le i$ et $2\le n\le1000$.