平方子序列

题目描述

给定一个由小写英文字母组成的字符串 $S$。 求满足以下条件的非空字符串 $T$ 的个数,对 $998244353$ 取模:

• 两个 $T$ 拼接而成的字符串 $TT$ 是 $S$ 的一个子序列(不要求连续)。

输入格式

输入按以下格式从标准输入给出:

$S$

输出格式

输出答案。

样例

ababbaba

8

满足条件的八个字符串为:a、aa、ab、aba、b、ba、bab、bb。

zzz

1

满足条件的字符串只有 z。 注意,虽然从 $S = S_1S_2S_3 =$ zzz 中提取子序列 zz 的方式有三种,即 $S_1S_2 =$ zz、$S_1S_3 =$ zz、$S_2S_3 =$ zz,但该字符串对答案的贡献只计算一次。

ppppqqppqqqpqpqppqpqqqqpppqppq

580

数据范围

• $S$ 是由小写英文字母组成的字符串,长度在 $1$ 到 $100$ 之间(含端点)。