题目描述

给定一个只包含小写英文字母的字符串 $S$。请输出满足以下条件的非空字符串 $T$ 的个数，对 $998244353$ 取模。

将 $T$ 连续连接两次得到的字符串 $TT$，可以作为 $S$ 的（不一定连续的）子序列出现。

输入格式

输入以以下格式从标准输入给出。

$S$

输出格式

请输出答案。

样例 1

输入

ababbaba

输出

8

样例 2

输入

zzz

输出

1

样例 3

输入

ppppqqppqqqpqpqppqpqqqqpppqppq

输出

580

说明/提示

限制条件

• $S$ 是一个只包含小写英文字母的字符串，长度满足 $1 \leq |S| \leq 100$。

样例解释 1

满足题目条件的字符串 $T$ 有 $8$ 个，分别是：a、aa、ab、aba、b、ba、bab、bb。

样例解释 2

满足题目条件的字符串 $T$ 只有 z。$S = S_1S_2S_3 = zzz$，可以通过 $S_1S_2 = zz$、$S_1S_3 = zz$、$S_2S_3 = zz$ 这三种方式得到字符串 zz 作为子序列，但字符串 z 只计入答案一次。

由 ChatGPT 4.1 翻译