تمتلك جامعة كيوتو شجرة رمزية رائعة كشجرة شعار لها.
لشدة إعجابه بهذه الشجرة الرمزية، صنع K-kun نسخة منها على شكل شجرة مجذرة تتكون من $N$ رؤوس.
رؤوس الشجرة مرقمة $1, 2, \dots, N$، وجذر الشجرة هو الرأس $1$، والحافة $i$ تصل بين الرأسين $u_i$ و $v_i$.
ولأنه رأى أن مجرد نسخ الشجرة سيكون غير ممتع، يكتب K-kun عدداً صحيحاً غير سالب على كل رأس من رؤوس الشجرة بحيث تتحقق الشروط التالية.
الشروط
- العدد الصحيح المكتوب على الجذر هو $K$.
- لكل رأس غير الجذر، يكون العدد الصحيح المكتوب على ذلك الرأس على الأكثر مساوياً للعدد الصحيح المكتوب على أبيه.
أوجد باقي قسمة عدد الطرق الممكنة لكتابة الأعداد الصحيحة على رؤوس الشجرة على $998244353$.
تُعتبر طريقتان لكتابة الأعداد الصحيحة على الرؤوس مختلفتين إذا وفقط إذا وُجد رأس ما يختلف العدد الصحيح المكتوب عليه بين الطريقتين.
الإدخال
يحتوي السطر الأول على العددين الصحيحين $N, K$ مفصولين بمسافات. ($2 \le N \le 3000, 1 \le K \le 10^9$)
يحتوي كل سطر من الأسطر الـ $N - 1$ التالية على عددين صحيحين $u_i, v_i$ مفصولين بمسافات، يمثلان حافة في الشجرة.
الإخراج
اطبع الإجابة بباقي القسمة على $998244353$.
أمثلة
مثال الإدخال 1
5 1 1 2 1 3 3 4 3 5
مثال الإخراج 1
10
مثال الإدخال 2
16 16 15 14 15 11 7 10 14 2 4 6 14 16 5 3 1 5 12 11 5 7 2 9 13 10 5 14 9 6 8 1
مثال الإخراج 2
623173536
ملاحظة
بالنسبة للمثال الأول، فإن التخصيصات الـ $10$ التالية للأعداد الصحيحة على الرؤوس $1, 2, 3, 4, 5$ تحقق الشروط.
- $1, 0, 0, 0, 0$
- $1, 0, 1, 0, 0$
- $1, 0, 1, 0, 1$
- $1, 0, 1, 1, 0$
- $1, 0, 1, 1, 1$
- $1, 1, 0, 0, 0$
- $1, 1, 1, 0, 0$
- $1, 1, 1, 0, 1$
- $1, 1, 1, 1, 0$
- $1, 1, 1, 1, 1$