시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 (추가 시간 없음) | 512 MB | 4 | 4 | 3 | 100.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$.
xxx
4
abacaba
80
ypiiouiuiputrhgogghjhp
1084841
dfgfhdgdhjgfdhgdfhgfdgfddfg
190900560
qweqwewqewqeqweqwqwewqrqwrrew
910048289
thosewereactuallykeyboardslaps
405649044