长度为 $k$ 的字符序列 $t$ 的回文度（palindromicity）是指满足 $0 \le i < k - 1 - i$ 且 $t_i = t_{k-1-i}$ 的索引 $i$ 的数量。注意，索引从 0 开始。

给你一个字符串 $s$。求其所有子序列的回文度之和。作为子序列出现多次的序列将被计算多次（即，无论它们是否相同，你需要对所有 $2^{|s|}$ 个子序列的回文度求和）。

输出正确答案模 998244353 的结果。正式地，如果实际答案为 $y$，而你的答案为 $x$，当 $-2^{63} \le x < 2^{63}$ 且 $x - y$ 能被 998244353 整除时，你的答案将被视为正确。

输入格式

唯一的一行包含一个非空字符串 $s$，由小写英文字母组成，长度不超过 123456。

输出格式

输出一个整数 —— $s$ 的所有子序列的回文度之和模 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