تلقى أليكسي شجرة تفاح بحجم $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\}$.