题目描述

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

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

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

输入描述

一个字符串，仅由小写字母组成，字符串长度不大于$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$

思路：思维题

给定一个字符串，求其有多少子序列满足首尾字符相同。

长度为1的子序列显然满足，当长度大于等于2时呢？

我们来看一个例子：abca。当长度大于等于2时，首先要确保首尾字符相同，这时，其中间的字符就可以任意选了。根据数学知识我们知道，当中间字符数为$x$时，选取任意个的方法有$2^x$种。

所以我们就只要找到两个相同字符后，直接计算答案即可。