题目描述

给定一个字符串，有多少子序列满足首尾字符是相同的？

注：子序列可以不连续，但是需要保证在原串中的顺序。

输入描述

一个字符串，仅由小写字母组成，字符串长度不大于$10^5。$

输出描述

满足条件的子序列的数量。由于答案过大，请将答案对于$998244353$取模

样例

输入

abca

输出

8

样例说明

长度为$1$的子序列均符合要求，共$4$个。

长度为$2$的子序列，有"ab","ac","aa","bc","ba","ca"，符合条件的有"aa"。

长度为$3$的子序列，有"abc","aba","aca","bca"，符合条件的有"aba","aca"。

长度为$4$的子序列，有"abca"，符合条件的有"abca"。

答案为$4 + 1+2+1=8$