23708번 - Filipp Rukhovich 다국어

문제

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ドル$.

제한

힌트