더 강한 Jovsi

Jovsi는 여전히 힘이 센 소년이다. 어릴 때부터 기관총을 좋아해서 자주 흉내를 냈는데, 이유는 알 수 없지만 trtrtrt나 bambambam이 아니라 acacacacac라고 외쳤다.

Malnar 씨는 Jovsi의 힘에는 감탄하지 않고, 그의 문제 해결 능력에만 관심이 있다. 어느 날 그는 왼쪽 끝에서 오른쪽 끝까지 $n$개의 글자가 적힌 막대를 Jovsi에게 선물했다.

Malnar 씨는 대칭인 막대를 아름답다고 여겨서 팰린드롬 쌍에 특히 관심이 많다. 팰린드롬 쌍은 $1 \le l \le r \le n$을 만족하는 자연수 순서쌍 $(l, r)$ 가운데, 위치 $l$부터 $r$까지의 글자로 만든 단어가 팰린드롬인 쌍이다. 팰린드롬은 앞에서 읽으나 뒤에서 읽으나 같은 단어다.

Malnar 씨는 Jovsi에게 도전 과제를 낸다. 도전 과제는 자연수 $k$와, $l_1 < l_2 < \cdots < l_k$이고 $r_1 > r_2 > \cdots > r_k$을 만족하는 $k$개의 팰린드롬 쌍 $(l_i, r_i)$의 수열로 이루어진다.

Jovsi는 어떤 상황에도 대비해야 하므로, Malnar 씨에게서 받을 수 있는 서로 다른 도전 과제가 몇 개인지 알고 싶어 한다. Jovsi를 도와 서로 다른 도전 과제의 개수를 998244353으로 나눈 나머지를 출력하라.

한 줄에 Malnar 씨의 막대에 적힌 글자의 나열인 문자열이 주어진다. 문자열은 소문자 영어 알파벳으로만 이루어지며, 길이는 최대 100만이다.

한 줄에 서로 다른 도전 과제의 개수를 998244353으로 나눈 나머지를 출력한다.