背景

原题来自 2025 年洛谷愚人节比赛的 F 题。

题目描述

给定一个字符串 $S$。

你有一个随机打字机。这个随机打字机打出的第一个字符一定是 $S$ 的第一位，之后打出的所有字符的概率分布只和它打出的上一个字符有关，并且按照如下规则进行：

• 将字符串 $S$ 首尾相接连成一个环，记录下每种字符的下一个字符的种类和出现次数；
• 那么，如果它打出的上一个字符是 $i$，此时它接下来打出字符 $j$ 的概率为 $\frac{cnt_{i,j}}{cnt_i}$。
• 其中，$cnt_i$ 为字符 $i$ 在 $S$ 中的出现次数，$cnt_{i,j}$ 为子串 $ij$ 在环状的 $S$ 中的出现次数。

每个新打出的字符会接在上一个打出的字符的后面。

当 $S$ （注意不是环状的 $S$）首次成为打字机打出的字符串的子串时，记录下当前打字机打出的字符总数。求这个总数的期望值模 $998244353$ 的结果。

输入格式

一行一个字符串 $S$，由大小写字母和数字组成。长度不超过 $300000$。

输出格式

一行一个整数表示答案模 $998244353$ 的结果。

123

3

1234

4

54321

5

123456

6

114

6

CCF

6

add

5

eleven

54

BV1fy411e7ue

645

提示

设 $n$ 为字符串的长度。

特殊性质 A：保证输入的字符串是由一个没有重复字符的字符串重复若干次得到，比如 cat，catcat，meowmeowmeow。

特殊性质 B：保证输入的字符串的首字母在字符串中出现恰好一次。