לאוניברסיטת קיוטו יש עץ סמלי מפואר המשמש כעץ הסמל שלה.
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$