بالنسبة لتبديل $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}$.