You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

塔子哥最近做了很多字符串的题目，普通的字符串题已经难不倒他了！

但是这次他遇到了一个难题：给定一个字符串，有多少子序列满足首尾字符是相同的？

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

输入描述

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

输出描述

满足条件的子序列的数量。由于答案过大，请将答案对于$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$