QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
Statistics

小 D 四岁半的时候学会了后缀自动机。

你有一个字符串 $S$,长度为 $n$。初始时,$T_0 = S$。每次你可以删除 $T_i$ 的开头或结尾的字符得到新的字符串 $T_{i+1}$,经过 $n-1$ 次操作之后,我们会得到只有一个字符的串 $T_{n-1}$,根据每次删除的选择,一共有 $2^{n-1}$ 中可能的操作序列。注意,虽然可能会有一次操作,删除开头或结尾的字符得到相同的串,但是我们仍然把它当成两种不一样的操作序列。

对于一个串 $T$,我们记 $occ(T)$ 表示 $T$ 在 $S$ 中作为子串的出现次数,比如 $occ(\textsf{aaa}, \textsf{aaabaaa}) = 3$。

对于一个操作序列,记它的贡献是 $\prod_{i=1}^{n-1} occ(T_i)$,求所有操作序列的贡献和,由于答案很大,输出对 $998\,244\,353$ 取模的结果。

输入格式

一共一行,包含一个字符串 $S$,保证 $S$ 只包含小写字符。

输出格式

一行一个整数,表示答案。

样例数据

样例 1 输入

zzz

样例 1 输出

24

样例 2 输入

abbab

样例 2 输出

53

样例 3

见下发文件。

子任务

一共 $20$ 个测试点。

对于测试点 $1 \sim 5$,满足 $|S| \leq 5\, 000$。

对于测试点 $6 \sim 8$,满足 $S$ 的每个字符从 ab 中等概率独立随机生成。

对于测试点 $9 \sim 14$,满足 $|S| \leq 6 \times 10^4$。

对于所有数据,$1 \leq |S| \leq 10^5$。