Aleksei ได้รับต้นแอปเปิลขนาด $n$ เป็นของขวัญวันเกิด ในฐานะนักเขียนโปรแกรมเชิงแข่งขัน เขาจึงตัดสินใจคำนวณจำนวนพายแอปเปิลขนาด $k$ ($k$-apple pies) บนต้นไม้นี้
ต้นแอปเปิลขนาด $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\}$