시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 (추가 시간 없음) 512 MB332100.000%

문제

The palindromicity of a sequence of characters $t$ of length $k$ is number of indices $i$, such that $0 \leq i < k - i - 1$ and $t_i = t_{k - 1 - i}$. Note that 0-based indexing is used.

You are given a string $s$. Count the sum of palindromicities over all its subsequences. Sequences which occur multiple times as a subsequence are counted multiple times (i.e. you sum palindromicities over all $2^{|s|}$ subsequences whether they are distinct or not).

Output the correct answer modulo $998244353$. Formally, if the actual answer is $y$ and your answer is $x$, it will be considered correct if $-2^{63} \leq x < 2^{63}$ and $x-y$ is divisible by $998244353$.     

입력

The only line contains a non-empty string $s$ of lowercase latin letters with length not exceeding $123456$. 

출력

Output a single integer --- sum of palindromicities over all subsequences of $s$ modulo $998244353$.

예제 입력 1

xxx

예제 출력 1

4

예제 입력 2

abacaba

예제 출력 2

80

예제 입력 3

ypiiouiuiputrhgogghjhp

예제 출력 3

1084841

예제 입력 4

dfgfhdgdhjgfdhgdfhgfdgfddfg

예제 출력 4

190900560

예제 입력 5

qweqwewqewqeqweqwqwewqrqwrrew

예제 출력 5

910048289

예제 입력 6

thosewereactuallykeyboardslaps

예제 출력 6

405649044