久莲 היא נערה שאוהבת לחבר בעיות.

לאחר סיום ה־World Final השנה, 久莲 התלהבה במיוחד מגאומטריה חישובית, ולכן החליטה לתת גם בתחרות NOI בעיית גאומטריה חישובית: זו בעיה שרק שמה קשור לגאומטריה חישובית.

ראשית, 久莲 נותנת עץ מושרש $T$ ובו $n$ צמתים ($n\ge2$), ששורשו הוא צומת מספר $1$. עלים מוגדרים ככל הצמתים, מלבד השורש, שדרגתם בדיוק $1$. באיור הבא דוגמה לעץ $T$, שקבוצת העלים שלו היא $\{3,4,5\}$.

לאחר מכן, באמצעות העץ, 久莲 בונה סדרה $A$:

• מבצעים סריקה לעומק של העץ כולו החל מהשורש, ובכל צומת מבקרים בילדיו בסדר עולה של מספריהם. כך מתקבל סדר DFS של העץ $T$.
• לפי סדר הופעתם בסדר ה־DFS, מההתחלה לסוף, 久莲 מסדרת את כל העלים בשורה ומקבלת את הסדרה $A$.

באמצעות $A$, 久莲 מגדירה גם את המרחק $d(u,v)$ בין שני עלים $u,v$: אם $u$ הוא האיבר ה־$i$ ב־$A$ ו־$v$ הוא האיבר ה־$j$, אז $d(u,v)=\min(|i-j|,|A|-|i-j|)$. כאן $|A|$ הוא אורך הסדרה, כלומר מספר העלים ב־$T$, ו־$i,j$ מציינים מיקומים הממוספרים החל מ־$1$.

בדוגמה לעיל, $A=[4,5,3]$ ומתקיים $d(3,5)=d(3,4)=d(4,5)=1$. מיקומיהם של $3,4,5$ הם $3,1,2$, בהתאמה.

לבסוף, 久莲 נותנת פרמטר $K$. באמצעות העץ המושרש $T$ והסדרה $A$, אפשר לבנות גרף לא מכוון $G$ ובו $n$ צמתים, ללא קשתות מקבילות וללא לולאות עצמיות: שני צמתים שונים $u,v$ מחוברים בקשת אם ורק אם הם מקיימים לפחות אחד מהתנאים הבאים:

• בעץ $T$ יש קשת המחברת את $u,v$.
• שני הצמתים $u,v$ הם עלים בעץ $T$, ומתקיים $d(u,v)\le K$.

כאשר $K=1$ או $K=2$, הגרף $G$ המתקבל מהדוגמה לעיל הוא הגרף שבאיור הבא בשני המקרים:

כעת 久莲 מבקשת שתחשבו כמה מעגלים המילטוניים שונים יש ב־$G$. התשובה עשויה להיות גדולה; הדפיסו אותה מודולו $998244353$.

להלן כמה הגדרות נוספות:

• מעגל המילטוני $H$ בגרף לא מכוון $G$ ללא קשתות מקבילות וללא לולאות עצמיות הוא תת־קבוצה של קשתות $G$, כך שלכל צומת בדיוק שתי קשתות שונות הנוגעות בו שייכות ל־$H$, ואפשר להגיע מכל צומת לכל צומת אחר, ישירות או בעקיפין, באמצעות קשתות $H$.
• שני מעגלים המילטוניים $H_1,H_2$ בגרף לא מכוון $G$ ללא קשתות מקבילות וללא לולאות עצמיות שונים אם ורק אם קיימת קשת $e$ השייכת ל־$H_1$ ואינה שייכת ל־$H_2$.

קלט

קראו את הנתונים מהקובץ polygon.in.

בשורה הראשונה שני מספרים שלמים $n,K$, מספר הצמתים בעץ $T$ והפרמטר $K$ שבחרה 久莲.

בשורה השנייה $n-1$ מספרים שלמים $f_i$ ($1\le f_i\le i$), כאשר $f_i$ מציין שבעץ $T$ קיימת קשת $(f_i,i+1)$.

פלט

כתבו את הפלט לקובץ polygon.out.

הדפיסו שורה ובה מספר שלם אחד: מספר המעגלים ההמילטוניים מודולו $998244353$.

דוגמאות

קלט 1

5 1
1 1 2 2

פלט 1

2

הסבר

דוגמה זו זהה לחלוטין לדוגמה שבגוף הבעיה. סדרי הצמתים בשני המעגלים ההמילטוניים הם $(1,2,4,5,3)$ ו־$(1,2,5,4,3)$.

תת־משימות

גודלי הנתונים ותכונותיהם בכל בדיקה מפורטים בטבלה הבאה:

בתכונה A מובטח שלכל צומת בעץ יש לכל היותר שני ילדים.

בכל הנתונים מובטח $1\le f_i\le i$ ו־$2\le n\le1000$.