题目背景

原题来自 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

提示

保证 $k$ 在模 $998244353$ 的意义下不为 $0$。

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

测试点编号	特殊性质 A	特殊性质 B	无特殊性质
$n\le 5$	1	2, 3	4, 5
$n\le 10$	6	7, 8	9, 10
$n\le 20$	11	12, 13	14, 15
$n\le 100$	16	17, 18	19, 20
$n\le 200$	21	22, 23	24, 25
$n\le 300$	26	27, 28	29, 30
$n\le 1000$	31	32, 33	34, 35
$n\le 2000$	36	37, 38	39, 40
$n\le 2\times 10^5$	41	42, 43	44, 45
$n\le 3\times 10^5$	46	47, 48	49, 50

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

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