강한 Jovsi

Jovsi는 힘이 센 소년이다. 어릴 때부터 기관총을 좋아해서 자주 흉내 냈는데, 이유는 모르겠지만 "trtrtrt"나 "bambambam"이 아니라 "acacacacac"이라고 외쳤다.

Malnar 씨는 Jovsi의 힘에는 관심이 없고, 그가 문제를 푸는 능력만 본다. 어느 날 Malnar 씨는 Jovsi에게 왼쪽 끝부터 오른쪽 끝까지 $n$개의 글자가 적힌 막대를 주었다. Malnar 씨는 대칭인 막대가 아름답다고 생각해서 회문 쌍에 특히 관심이 많다. 회문 쌍은 $1 \le l \le r \le n$을 만족하는 자연수 순서쌍 $(l, r)$ 가운데, 위치 $l$부터 $r$까지의 글자로 만든 단어가 회문인 것을 말한다. 회문은 왼쪽에서 읽든 오른쪽에서 읽든 같은 단어이다.

Malnar 씨는 이어서 Jovsi에게 도전 문제를 냈다. 도전 문제는 자연수 $k$와 $k$개의 회문 쌍 $(l_i, r_i)$의 수열로 이루어진다. 이 수열은 $l_1 < l_2 < \dots < l_k$이고 $r_1 > r_2 > \dots > r_k$를 만족한다.

Jovsi는 어떤 상황에도 대비해야 하므로, 받을 수 있는 서로 다른 도전 문제가 몇 개인지 알고 싶어 한다. 그 개수를 세어 달라. 답은 $998244353$으로 나눈 나머지로 출력한다.

입력은 소문자 영어 알파벳으로 이루어진 단어가 한 줄에 주어진다. 이 단어는 Malnar 씨의 막대에 적힌 글자의 순서이다. 단어의 길이는 최대 $10^6$이다.

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