Jiulian ist ein Mädchen, das gerne Aufgaben entwirft.

Nach dem diesjährigen World Final begeistert sich Jiulian besonders für algorithmische Geometrie und möchte deshalb auch bei der NOI eine Geometrieaufgabe stellen: eine Aufgabe, bei der nur der Name mit algorithmischer Geometrie zu tun hat.

Zunächst gibt Jiulian einen verwurzelten Baum $T$ mit $n$ Knoten und $n\ge2$ vor. Die Wurzel hat die Nummer $1$. Als Blätter bezeichnen wir alle Knoten außer der Wurzel, deren Grad genau $1$ ist. Die folgende Abbildung zeigt einen Beispielbaum $T$ mit der Blattmenge $\{3,4,5\}$.

Aus diesem Baum konstruiert Jiulian anschließend eine Folge $A$:

• Durchlaufe den gesamten Baum ab der Wurzel mit einer Tiefensuche. Besuche die Kinder dabei in aufsteigender Reihenfolge ihrer Nummern. So erhältst du eine DFS-Reihenfolge von $T$.
• Ordne dann alle Blätter nach ihrem Auftreten in dieser DFS-Reihenfolge von vorne nach hinten an. Dies ergibt die Folge $A$.

Mithilfe der Folge $A$ definiert Jiulian weiter den Abstand $d(u,v)$ zweier Blätter $u,v$: Ist $u$ das $i$-te und $v$ das $j$-te Element von $A$, so ist $d(u,v)=\min(|i-j|,|A|-|i-j|)$. Dabei ist $|A|$ die Länge der Folge, also die Anzahl der Blätter von $T$. Die Positionen $i,j$ werden beginnend mit $1$ gezählt.

Im obigen Beispiel ist $A=[4,5,3]$. Es gilt $d(3,5)=d(3,4)=d(4,5)=1$, und die Positionen von $3,4,5$ sind der Reihe nach $3,1,2$.

Schließlich gibt Jiulian einen Parameter $K$ vor. Aus dem verwurzelten Baum $T$ und der Folge $A$ können wir einen ungerichteten Graphen $G$ ohne Mehrfachkanten und Schleifen mit $n$ Knoten konstruieren. Zwei verschiedene Knoten $u,v$ sind genau dann durch eine Kante verbunden, wenn mindestens eine der folgenden Bedingungen erfüllt ist:

• Im Baum $T$ gibt es eine Kante zwischen $u,v$.
• Im Baum $T$ sind $u,v$ beide Blätter, und es gilt $d(u,v)\le K$.

Für $K=1$ oder $K=2$ ergibt das obige Beispiel jeweils den in der folgenden Abbildung gezeigten Graphen $G$:

Jiulian möchte nun, dass du die Anzahl verschiedener Hamiltonkreise in $G$ berechnest. Die Antwort kann groß sein; gib sie modulo $998244353$ aus.

Es folgen einige ergänzende Definitionen:

• Ein Hamiltonkreis $H$ eines ungerichteten Graphen $G$ ohne Mehrfachkanten und Schleifen ist eine Teilmenge der Kanten von $G$. Jeder Knoten hat genau zwei verschiedene anliegende Kanten in $H$, und je zwei beliebige Knoten sind durch Kanten aus $H$ direkt oder indirekt miteinander erreichbar.
• Zwei Hamiltonkreise $H_1,H_2$ eines ungerichteten Graphen $G$ ohne Mehrfachkanten und Schleifen sind genau dann verschieden, wenn eine Kante $e$ existiert, die in $H_1$, aber nicht in $H_2$ liegt.

Eingabe

Lies die Daten aus der Datei polygon.in.

Die erste Zeile enthält zwei ganze Zahlen $n,K$, die Anzahl der Knoten von $T$ und Jiulians gewählten Parameter $K$.

Die zweite Zeile enthält $n-1$ ganze Zahlen $f_i$ mit $1\le f_i\le i$. Dabei gibt $f_i$ an, dass der Baum $T$ die Kante $(f_i,i+1)$ enthält.

Ausgabe

Schreibe die Ausgabe in die Datei polygon.out.

Gib eine Zeile mit einer ganzen Zahl aus: der Anzahl der Hamiltonkreise modulo $998244353$.

Beispiele

Eingabe 1

5 1
1 1 2 2

Ausgabe 1

2

Hinweis

Dieses Beispiel ist genau das Beispiel aus der Aufgabenstellung. Die beiden Hamiltonkreise durchlaufen die Knoten in den Reihenfolgen $(1,2,4,5,3)$ beziehungsweise $(1,2,5,4,3)$.

Teilaufgaben

Die Datenbereiche und Eigenschaften der einzelnen Testpunkte stehen in der folgenden Tabelle:

Eigenschaft A garantiert, dass jeder Knoten des Baums höchstens zwei Kinder hat.

Für alle Daten ist garantiert: $1\le f_i\le i$ und $2\le n\le1000$.