สำหรับการเรียงสับเปลี่ยน $p$ ที่มีความยาว $n$ เรานิยามให้ $f(p)$ แทนเซตของตำแหน่งที่เป็นค่าสูงสุดของส่วนนำ (prefix maximum) กล่าวคือ $f(p) = \{i \mid 1 \le i \le n, \text{ s.t. } \forall 1 \le j < i, p_i > p_j\}$
ในทำนองเดียวกัน ให้ $g(p)$ แทนเซตของค่าตัวเลขที่เป็นค่าสูงสุดของส่วนนำ นั่นคือ $g(p) = \{p_i \mid i \in f(p)\}$
ตอนนี้มีการสุ่มเลือกการเรียงสับเปลี่ยน $k$ ชุด ได้แก่ $p_1, p_2, \ldots, p_k$ อย่างเป็นอิสระและด้วยความน่าจะเป็นเท่ากันจากการเรียงสับเปลี่ยนความยาว $n$ ทั้งหมด (สามารถซ้ำกันได้) Little A ต้องการทราบว่าจะมี $g(p)$ ที่แตกต่างกันอย่างแท้จริงโดยคาดหวังกี่เซตในบรรดาการเรียงสับเปลี่ยนเหล่านี้ เป้าหมายคือการหาว่าในบรรดา $g(p_1), g(p_2), \ldots, g(p_k)$ มีเซตที่แตกต่างกันโดยคาดหวังกี่เซต? ให้แสดงคำตอบเป็นผลลัพธ์มอดูโล $998244353$
ข้อมูลนำเข้า
บรรทัดเดียวประกอบด้วยจำนวนเต็มสองตัว $n, k$ ($1 \le n, k \le 5000$)
ข้อมูลส่งออก
บรรทัดเดียวประกอบด้วยจำนวนเต็มหนึ่งตัว แทนผลลัพธ์ของคำตอบมอดูโล $998244353$
ตัวอย่าง
ข้อมูลนำเข้า 1
1 1
ข้อมูลส่งออก 1
1
ข้อมูลนำเข้า 2
3 2
ข้อมูลส่งออก 2
388206139
ข้อมูลนำเข้า 3
3 4
ข้อมูลส่งออก 3
408232647
ข้อมูลนำเข้า 4
112 646
ข้อมูลส่งออก 4
928854225
หมายเหตุ
สำหรับตัวอย่างแรก คำตอบคือ $1$
สำหรับตัวอย่างที่สอง คำตอบคือ $\frac{31}{18}$
สำหรับตัวอย่างที่สาม คำตอบคือ $\frac{1711}{648}$