Ұзындығы $n$ болатын $p$ алмастыруы үшін $f(p)$ арқылы префикстік максимумдардың орындарының жиынын белгілейміз. Нақтырақ айтқанда, $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)\}$.
Енді ұзындығы $n$ болатын барлық алмастырулардың ішінен тәуелсіз және бірқалыпты кездейсоқ түрде таңдалған $k$ алмастыру $p_1, p_2, \ldots, p_k$ берілген (қайталануы мүмкін). Кішкентай 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}$.