มหาวิทยาลัยเกียวโตมีต้นไม้สัญลักษณ์อันงดงามเป็นต้นไม้ประจำมหาวิทยาลัย
ด้วยความประทับใจในต้นไม้สัญลักษณ์นี้ 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
หมายเหตุ
สำหรับตัวอย่างแรก การกำหนดจำนวนเต็มให้กับจุดยอด $1, 2, 3, 4, 5$ ทั้ง $10$ แบบต่อไปนี้สอดคล้องกับเงื่อนไข
- $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$