解题思路

本题要求统计所有“同源游走”的数量。游走本质上是从标牌序列中按原顺序选出的一个非空子序列，并且要求子序列的首尾房间标牌字母相同。

1. 分类统计：

   • 长度为 1 的游走：起点与终点是同一个房间，首尾字母天然相同，共有 $n$ 条（其中 $n$ 为字符串长度）。
   • 长度大于等于 2 的游走：需要首尾字母相同，中间的房间可以任意选择参观或不参观。假设选择了位置 $i$ 和 $j$ 作为起止房间（$i<j$），且 $s[i]=s[j]$，则中间有 $j-i-1$ 个房间，每个房间可选或不选，方案数为 $2^{j-i-1}$。

2. 优化计算：

题目内容

在一个由 $n$ 个房间排成一排的走廊中，每个房间的门口挂着一个由小写字母制成的标牌。你计划从某个房间出发，按照从左到右的顺序依次参观若干个房间，并在某个房间结束参观——整个行程所经过的房间序列（包括起点和终点）称为一条“游走”。如果一条游走的起点房间与终点房间的标牌字母相同，则称其为“同源游走”。注意：你可以在任意房间停下，也可以只参观一个房间（此时起点与终点是同一房间，字母自然相同，也算作一条同源游走）。

现在给定这排房间的标牌序列，请问总共有多少条不同的同源游走？答案可能很大，请将其对 $998244353$ 取模后输出。

在这里，“游走”本质上是原序列的一个非空子序列，且必须保持原顺序。子序列通过选取原序列中的若干位置（至少一个）得到，首尾位置的字符相同。

约束：

• 字符串仅由小写字母组成。
• 字符串长度不超过 $10^5$。

输入描述

输入仅有一行，包含一个由小写字母组成的字符串 $s$，长度为 $n$，满足 $1 \le n \le 10^5$。

输出描述

输出一个整数，表示所有同源游走的数量对 $998244353$ 取模的结果。

样例1

输入

a

输出

1

说明

字符串长度为 1，只有一条游走，即参观该房间。起始与结束字母均为 'a'，是同源游走。故答案为 1。

样例2

输入

abc

输出

3

说明

字符串由三个不同字母组成，没有任何两个房间字母相同。因此只有每个房间单独作为游走，共 3 条。分别为 'a'、'b'、'c'。

样例3

输入

abab

输出

8

说明

字符串 s = "abab"，字母 'a' 出现在位置 1 和 3；字母 'b' 出现在位置 2 和 4。 对于 'a'：选择起点和终点均为位置 1（1 条）；均为位置 3（1 条）；起点位置 1 终点位置 3，中间有位置 2 可选可不选，有 $2^{1} = 2$ 条游走（"aa" 和 "aba"）。'a' 共贡献 $1+1+2=4$ 条。 同理 'b'：起点终点均为位置 2（1 条）；均为位置 4（1 条）；起点 2 终点 4，中间位置 3 可选可不选，有 $2^{1}=2$ 条。'b' 共贡献 4 条。 总计 $4+4=8$ 条。

样例4

输入

aaaa

输出

15

说明

所有房间字母相同，任何非空子序列首尾字母均为 'a'。总共有 $2^4 - 1 = 15$ 条非空子序列，因此答案为 15。也可由求和公式 $\sum_{1\le i\le j\le 4} 2^{j-i-1}$ 计算得到 15。