임베딩

길이가 $n$인 문자열 $A$가 주어진다. $A$의 회문 부분 문자열을 생각하자. 부분 문자열은 시작 위치 $s$와 끝 위치 $e$($1 \le s \le e \le n$)로 정해지며, 모든 정수 $i$ ($0 \le i \le e-s$)에 대해 $A[s+i]=A[e-i]$이면 회문이다.

깊이 $k \ge 1$의 임베딩은 $k$개의 회문 부분 문자열로 이루어진 수열로, $s_1 < \ldots < s_k$이고 $e_1 > \ldots > e_k$를 만족한다. 즉 회문들이 러시아 인형처럼 엄격하게 안쪽으로 포함된다. $A$의 임베딩 개수를 구하라.

문자열 $A$를 담은 한 줄이 주어진다. 문자열은 비어 있지 않고, 길이는 최대 $10^6$이며, 영어 소문자로만 이루어진다.

임베딩의 개수를 $998\,244\,353$으로 나눈 나머지를 출력한다.

문자열 bonobo에서 깊이 1인 임베딩은 9개, 깊이 2인 임베딩은 6개, 깊이 3인 임베딩은 1개로, 총 16개이다.