#P3723. 「SDOI / SXOI2022」子串统计

「SDOI / SXOI2022」子串统计

题目描述

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

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

对于一个串 TT,我们记 occ(T)\operatorname{occ}(T) 表示 TTSS 中作为子串的出现次数,比如 occ(aaa,aaaabaaa)=3\operatorname{occ}(\mathtt{aaa,aaaabaaa})=3

对于一个操作序列,记它贡献是

$$\prod_{i=1}^{n-1} \operatorname{occ}\left(T_{i}\right) $$

求出所有操作序列的贡献和,由于答案很大,请输出答案对 998244353998244353 取模的结果。

输入格式

只有一行一个字符串 SS,保证只包含小写字符。

输出格式

输出一行一个整数表示答案。

zzz

24

abbab

53

样例 3

见附加样例文件中的 ex_substring3.inex_substring3.out

数据范围与提示

本题共 2020 个测试点。

  • 对于测试点 151 \sim 5,满足 S5000|S| \leq 5000
  • 对于测试点 686 \sim 8,满足 SS 的每个字符均从 a\mathtt{a}b\mathtt{b} 中等概率独立随机生成。
  • 对于测试点 9149 \sim 14,满足 S6×104|S| \leq 6 \times 10^{4}

对于所有数据,1S1051 \leq|S| \leq 10^{5}SS 中只有小写英文字母。