Filipp Rukhovich

Time limit6sMemory limit512 MB

Summary

Sum the palindromicity of every subsequence of a string, counting each occurrence of a subsequence, modulo 998244353.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Math, String
Solved: No attempts yet

Problem

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

You are given a string $s$ . Count the sum of palindromicities over all its subsequences. Sequences that occur multiple times as a subsequence are counted multiple times. That is, you sum palindromicities over all $2^{|s|}$ subsequences, whether they are distinct or not.

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

Input

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

Output

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

Examples5

Example 1
Input
```
xxx
```
Expected output
```
4
```
Example 2
Input
```
abacaba
```
Expected output
```
80
```
Example 3
Input
```
ypiiouiuiputrhgogghjhp
```
Expected output
```
1084841
```
Example 4
Input
```
dfgfhdgdhjgfdhgdfhgfdgfddfg
```
Expected output
```
190900560
```

Example 5

Input

qweqwewqewqeqweqwqwewqrqwrrew

Expected output

910048289