Pituutta $n$ olevalle permutaatiolle $p$ määrittelemme joukon $f(p)$ kuvaamaan etuliitteen maksimin (prefix maximum) sijainteja. Tarkemmin sanottuna $f(p) = \{i \mid 1 \le i \le n, \text{ s.t. } \forall 1 \le j < i, p_i > p_j\}$.
Vastaavasti olkoon $g(p)$ etuliitteen maksimien lukuarvojen joukko, eli $g(p) = \{p_i \mid i \in f(p)\}$.
Nyt valitaan $k$ permutaatiota $p_1, p_2, \ldots, p_k$ riippumattomasti ja tasajakautuneen satunnaisesti kaikkien pituutta $n$ olevien permutaatioiden joukosta (toistot ovat sallittuja). Pikku A haluaa tietää, kuinka monta olennaisesti erilaista joukkoa $g(p)$ näiden permutaatioiden joukossa on odotusarvoisesti. Tavoitteena on selvittää, kuinka monta olennaisesti erilaista joukkoa on odotusarvoisesti joukkojen $g(p_1), g(p_2), \ldots, g(p_k)$ keskuudessa. Vastaus tulee tulostaa modulo $998244353$.
Syöte
Yksi rivi, joka sisältää kaksi kokonaislukua $n, k$ ($1 \le n, k \le 5000$).
Tuloste
Yksi rivi, joka sisältää kokonaisluvun: vastauksen arvon modulo $998244353$.
Esimerkit
Syöte 1
1 1
Tuloste 1
1
Syöte 2
3 2
Tuloste 2
388206139
Syöte 3
3 4
Tuloste 3
408232647
Syöte 4
112 646
Tuloste 4
928854225
Huomautus
Ensimmäisessä esimerkissä vastaus on $1$.
Toisessa esimerkissä vastaus on $\frac{31}{18}$.
Kolmannessa esimerkissä vastaus on $\frac{1711}{648}$.