20325번 - Jači Jovsi 다국어

Jovsi je i dalje jak dječak. Od malena je volio strojnice pa je ih je često volio imitarti, samo iz nekog razloga nije vikao trtrtrt ili bambambam, nego acacacacac.

Gospodin Malnar nije impresioniran Jovsijevom snagom te ga isključivo zanima njegova sposobnost rješavanja zadataka. Tako mu je jednog dana poklonio štap na kojemu je od lijevog do desnog kraja ispisano n slova. Gospodin Malnar smatra da su simetrični štapovi jako lijepi, zato ga posebno zanimaju palindromski parovi. To su uređeni parovi prirodnih brojeva (l, r), gdje 1 ≤ l ≤ r ≤ n, takvi da je riječ dobivena gledajući samo slova od l-te do r-te pozicije palindrom. Podsjetimo se da je palindrom riječ koja se čita jednako slijeva nadesno kao i zdesna nalijevo.

Gospodin Malnar je zatim odlučio Jovsiju zadati izazov. Izazov se sastoji od prirodnog broja k te niza od k palindromskih parova (l_i, r_i) za koje vrijedi l₁ < l₂ < · · · < l_k te r₁ > r₂ > · · · > r_k.

Jovsi mora biti spreman na svaku situaciju pa ga zanima koliko postoji različitih izazova koje može dobiti od gospodina Malnara. Pomozite Jovsiju i ispišite koliko postoji različitih izazova, modulo 998244353.

U jedinom je retku riječ koja se sastoji od malih slova engleske abecede, a predstavlja niz slova ispisanih na štapu gospodina Malnara. Riječ će se sastojati od najviše milijun znakova.

U jedinom retku potrebno je ispisati ostatak pri dijeljenju broja različith izazova s 998244353.