มีกล่องที่มีป้ายกำกับด้วยจำนวนเต็มแต่ละตัวตั้งแต่ $1$ ถึง $N$ กล่องละหนึ่งใบ นอกจากนี้ สำหรับจำนวนเต็มแต่ละตัวตั้งแต่ $1$ ถึง $N$ จะมีลูกบอล $M$ ลูกที่มีป้ายกำกับด้วยจำนวนเต็มนั้น
ลูกบอลทั้ง $NM$ ลูกนี้จะถูกสุ่มสลับแล้วแจกจ่ายลงในกล่อง $N$ ใบ โดยมีลูกบอลถูกใส่ลงในแต่ละกล่องเป็นจำนวน $M$ ลูกพอดี
มีวิธีที่เป็นไปได้ในการใส่ลูกบอลทั้งหมด $\frac{(NM)!}{(M!)^N}$ วิธี (หากถือว่าลูกบอลทุกลูกสามารถแยกแยะออกจากกันได้) และการจัดเรียงทั้งหมดนี้มีโอกาสเกิดขึ้นเท่ากัน
คุณจะทำการดำเนินการกับกล่องและลูกบอลเหล่านี้ การดำเนินการหนึ่งครั้งประกอบด้วยขั้นตอนต่อไปนี้
- เลือกกล่องหนึ่งใบแล้วเดินไปที่หน้ากล่องนั้น
- หากไม่มีลูกบอลอยู่ในกล่องนั้น ให้จบการดำเนินการ
- เลือกลูกบอลลูกใดก็ได้หนึ่งลูกจากกล่องนั้น แล้วทิ้งออกไปนอกกล่อง
- สุดท้าย เดินไปที่หน้ากล่องที่มีป้ายกำกับตรงกับป้ายกำกับของลูกบอลที่เพิ่งถูกทิ้งไปล่าสุด แล้วกลับไปที่ขั้นตอนที่ $2$
กำหนดให้คะแนนของคุณคือจำนวนครั้งของการดำเนินการที่ต้องใช้จนกว่าลูกบอลทั้ง $NM$ ลูกจะถูกทิ้งไปทั้งหมด คุณต้องการทำให้คะแนนนี้มีค่าน้อยที่สุด
จงหาค่าคาดหมายของคะแนนเมื่อคุณดำเนินการอย่างเหมาะสมที่สุด มอดูโล $998244353$
Input
บรรทัดแรกประกอบด้วย $N$ และ $M$ ตามลำดับนี้ คั่นด้วยช่องว่าง ($1 \le N \le 10^5, 1 \le M \le 100$)
Output
พิมพ์คำตอบออกมา
Examples
Input 1
2 2
Output 1
166374060
Input 2
3 1
Output 2
831870296
Input 3
100000 100
Output 3
402978825
Note
สำหรับตัวอย่างแรก การจัดเรียงลูกบอลที่เป็นไปได้และวิธีการดำเนินการที่เหมาะสมที่สุดที่สอดคล้องกันมีดังนี้
- ใส่ลูกบอลที่มีป้ายกำกับ $1$ สองลูกลงในกล่อง $1$ และใส่ลูกบอลที่มีป้ายกำกับ $2$ สองลูกลงในกล่อง $2$ (ความน่าจะเป็น $1/6$)
- ในการดำเนินการครั้งแรก เดินไปที่หน้ากล่อง $1$ จากนั้นหยิบลูกบอลที่มีป้ายกำกับ $1$ ออกมาหนึ่งลูกแล้วเดินไปที่หน้ากล่อง $1$ จากนั้นหยิบลูกบอลที่มีป้ายกำกับ $1$ ออกมาอีกลูกแล้วเดินไปที่หน้ากล่อง $1$ อีกครั้ง ณ จุดนี้ กล่อง $1$ ว่างเปล่าแล้ว จึงจบการดำเนินการ
- ในการดำเนินการครั้งที่สอง เดินไปที่หน้ากล่อง $2$ จากนั้นหยิบลูกบอลที่มีป้ายกำกับ $2$ ออกมาหนึ่งลูกแล้วเดินไปที่หน้ากล่อง $2$ จากนั้นหยิบลูกบอลที่มีป้ายกำกับ $2$ ออกมาอีกลูกแล้วเดินไปที่หน้ากล่อง $2$ อีกครั้ง ณ จุดนี้ กล่อง $2$ ว่างเปล่าแล้ว จึงจบการดำเนินการ
- ในกรณีนี้ คะแนนน้อยที่สุดที่ทำได้คือ $2$
- ใส่ลูกบอลที่มีป้ายกำกับ $1$ หนึ่งลูกและลูกบอลที่มีป้ายกำกับ $2$ หนึ่งลูกลงในแต่ละกล่องของกล่อง $1$ และกล่อง $2$ (ความน่าจะเป็น $2/3$)
- ในการดำเนินการครั้งแรก เดินไปที่หน้ากล่อง $1$ จากนั้นหยิบลูกบอลที่มีป้ายกำกับ $1$ ออกมาหนึ่งลูกแล้วเดินไปที่หน้ากล่อง $1$ จากนั้นหยิบลูกบอลที่มีป้ายกำกับ $2$ ออกมาหนึ่งลูกแล้วเดินไปที่หน้ากล่อง $2$ จากนั้นหยิบลูกบอลที่มีป้ายกำกับ $2$ ออกมาหนึ่งลูกแล้วเดินไปที่หน้ากล่อง $2$ จากนั้นหยิบลูกบอลที่มีป้ายกำกับ $1$ ออกมาหนึ่งลูกแล้วเดินไปที่หน้ากล่อง $1$ ณ จุดนี้ กล่อง $1$ ว่างเปล่าแล้ว จึงจบการดำเนินการ
- ในกรณีนี้ คะแนนน้อยที่สุดที่ทำได้คือ $1$
- ใส่ลูกบอลที่มีป้ายกำกับ $2$ สองลูกลงในกล่อง $1$ และใส่ลูกบอลที่มีป้ายกำกับ $1$ สองลูกลงในกล่อง $2$ (ความน่าจะเป็น $1/6$)
- ในการดำเนินการครั้งแรก เดินไปที่หน้ากล่อง $1$ จากนั้นหยิบลูกบอลที่มีป้ายกำกับ $2$ ออกมาหนึ่งลูกแล้วเดินไปที่หน้ากล่อง $2$ จากนั้นหยิบลูกบอลที่มีป้ายกำกับ $1$ ออกมาหนึ่งลูกแล้วเดินไปที่หน้ากล่อง $1$ จากนั้นหยิบลูกบอลที่มีป้ายกำกับ $2$ ออกมาหนึ่งลูกแล้วเดินไปที่หน้ากล่อง $2$ จากนั้นหยิบลูกบอลที่มีป้ายกำกับ $1$ ออกมาหนึ่งลูกแล้วเดินไปที่หน้ากล่อง $1$ ณ จุดนี้ กล่อง $1$ ว่างเปล่าแล้ว จึงจบการดำเนินการ
- ในกรณีนี้ คะแนนน้อยที่สุดที่ทำได้คือ $1$
โดยสรุป คะแนนน้อยที่สุดเป็น $2$ ด้วยความน่าจะเป็น $1/6$ และคะแนนน้อยที่สุดเป็น $1$ ด้วยความน่าจะเป็น $5/6$ ดังนั้นคะแนนคาดหมายโดยรวมคือ $7/6$ เพราะฉะนั้นจึงแสดงผล $166374060$ ซึ่งเป็นค่านี้มอดูโล $998244353$
นิยามของค่าคาดหมายมอดูโล $998244353$
สามารถพิสูจน์ได้ว่าค่าคาดหมายที่ต้องการหาเป็นจำนวนตรรกยะเสมอ นอกจากนี้ ภายใต้ข้อจำกัดของปัญหานี้ หากเขียนค่าคาดหมายในรูปเศษส่วนอย่างต่ำ $\frac{y}{x}$ รับประกันว่า $x$ จะไม่ถูกหารด้วย $998244353$ ลงตัว
ในกรณีนี้ จะมีจำนวนเต็ม $z$ เพียงตัวเดียวที่อยู่ระหว่าง $0$ ถึง $998244352$ (รวมขอบ) ซึ่งสอดคล้องกับ $xz \equiv y \pmod{998244353}$ จงแสดงผลค่า $z$ นี้