Jaki Jovsi
시간 제한1초메모리 제한512 MB
길이가 최대 백만인 소문자 문자열이 주어질 때, l이 증가하고 r이 감소하는 팰린드롬 부분 문자열들의 중첩 수열의 개수를 998244353으로 나눈 나머지를 구한다.
문제
Jovsi je 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 (li, ri) za koje vrijedi l1 < l2 < . . . < lk te r1 > r2 > . . . > rk.
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.