配点 : 100 点
問題文
文字列 S ,满足以下条件的长度 1 或更多字符串 当 A, B 存在时,S 说:“这是 Gomamayo desu。” 等于按此顺序用
- S 是 A 和 B 连接的字符串, A 的最后一个字符和 B 的第一个字符相等。
例如,字符串 abba 呀
名为 abbcddc 是芝麻,但是 ababa 不是芝麻蛋黄酱。
小写英文字母组成的字符串 S 。(i, j) (1 \leq i \leq j \leq |S|), S 的 可以考虑 i 从第一个字符开始 j 计算第一个字符之前分隔的连续子字符串的数量。 除以 998244353 求余数。
制約
- 1 \leq |S| \leq 10^{6}
- S 是一串小写字母
入力
输入是按以下格式从标准输入给出的。
S
出力
答案 1 行。
入力例 1
abbcc
出力例 1
8
bb, cc, abb, bbc, bcc, abbc, bbcc, abbcc 是芝麻,所以 (2, 3), (4, 5), (1, 3), (2, 4), (3, 5), (1, 4), (2, 5), (1, 5) 满足条件。
除了这些之外 (i,j) 不满足条件。
有
入力例 2
ssss
出力例 2
6
入力例 3
kotamanegi
出力例 3
0