시간 제한메모리 제한제출정답맞힌 사람정답 비율
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