Filipp Rukhovich

길이 $k$인 문자 수열 $t$의 팰린드롬성은 $0 \leq i < k - i - 1$이고 $t_i = t_{k-1-i}$인 인덱스 $i$의 개수이다. 인덱스는 0부터 시작한다.

문자열 $s$가 주어진다. 모든 부분수열에 대한 팰린드롬성의 합을 구하여라. 부분수열로서 여러 번 나타나는 수열은 여러 번 센다. 즉, 서로 같은지와 무관하게 $2^{|s|}$개의 모든 부분수열에 대해 팰린드롬성의 합을 구한다.

정답을 $998244353$으로 나눈 나머지를 출력하여라. 형식적으로, 실제 답이 $y$이고 출력한 답이 $x$일 때 $-2^{63} \leq x < 2^{63}$이고 $x-y$가 $998244353$으로 나누어떨어지면 정답으로 인정된다.

첫째 줄에 길이가 $123456$ 이하인, 영소문자로 이루어진 비어 있지 않은 문자열 $s$가 주어진다.

$s$의 모든 부분수열에 대한 팰린드롬성의 합을 $998244353$으로 나눈 나머지를 한 줄에 출력한다.