אלכסיי קיבל עץ תפוחים בגודל $n$ כמתנת יום הולדת. כמתכנת תחרותי בעצמו, הוא החליט לחשב את מספר פשטידות ה-$k$-תפוחים שעל העץ.
עץ תפוחים בגודל $n$ מוגדר כעץ מושרש עם $n$ צמתים, ששורשו בצומת $1$, שבו לכל צומת יש פחות ממש בנים ישירים מאשר להורה שלו (למעט השורש שאין לו הורה).
פשטידת $k$-תפוחים היא זוג $(v, S)$ שבו:
- $v \in V$ הוא צומת של העץ (המרכז),
- $S \subset V \setminus \{v\}$ היא קבוצת צמתים בגודל $k - 1$,
- קיים מספר שלם $d$ כך שלכל $u \in S$ מתקיים $\text{dist}(v, u) = d$.
המרחק $\text{dist}(u, v)$ מוגדר כמספר הקשתות במסלול הפשוט שבין הצמתים $u$ ו-$v$.
במילים אחרות, פשטידת $k$-תפוחים מורכבת מצומת אחד $v$ (המרכז) ומ-$k - 1$ צמתים אחרים שכולם נמצאים באותו מרחק מ-$v$.
המשימה שלכם היא לחשב את מספר פשטידות ה-$k$-תפוחים בעץ הנתון.
מאחר שהתשובה עלולה להיות גדולה, הדפיסו אותה מודולו $998\,244\,353$.
קלט
כל בדיקה מכילה מספר מקרי בדיקה. השורה הראשונה מכילה את מספר מקרי הבדיקה $t$ ($1 \le t \le 10^4$). אחריה מופיע תיאור מקרי הבדיקה.
כל מקרה בדיקה מתחיל בשורה המכילה שני מספרים שלמים $n$ ו-$k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): מספר הצמתים בעץ התפוחים וגודל פשטידת התפוחים.
השורה הבאה מכילה $n - 1$ מספרים שלמים $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), כאשר $p_i$ מציין את ההורה של צומת $i$ בעץ התפוחים.
סכום ה-$n$ על פני כל מקרי הבדיקה אינו עולה על $5 \cdot 10^5$.
פלט
עבור כל מקרה בדיקה, הדפיסו מספר שלם יחיד: מספר פשטידות ה-$k$-תפוחים מודולו $998\,244\,353$.
דוגמאות
קלט 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
פלט 1
1 20 16
הערה
במקרה הבדיקה הראשון, הפשטידה היחידה שקיימת ממורכזת בצומת $1$, והקבוצה המתאימה היא $S = \{2, 3\}$.