题目描述

英小文字のみからなる文字列 $S$ が与えられます。 下記の条件を満たす空でない文字列 $T$ の個数を $998244353$ で割ったあまりを出力してください。

$T$ を $2$ つ連結して得られる文字列 $TT$ が、$S$ に（連続とは限らない）部分列として含まれる。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$

输出格式

答えを出力せよ。

题目大意

给定一个由小写英文字母组成的字符串 $S$。计算满足以下条件的非空字符串 $T$ 的数量，答案对 $998244353$ 取模。

将 $T$ 复制一倍形成 $TT$，则 $TT$ 是 $S$ 的子序列（不一定连续）。

ababbaba

8

zzz

1

ppppqqppqqqpqpqppqpqqqqpppqppq

580

提示

制約

• $S$ は英小文字のみからなる長さ $1$ 以上 $100$ 以下の文字列

Sample Explanation 1

問題文中の条件を満たす文字列 $T$ は、a 、aa 、ab 、aba 、b 、ba 、bab 、bb の $8$ 個です。

Sample Explanation 2

問題文中の条件を満たす文字列 $T$ は、z のみです。 $S\ =\ S_1S_2S_3\ =$ zzz から、文字列 zz を部分列として得る方法は、 $S_1S_2\ =$ zz 、$S_1S_3\ =$ zz 、$S_2S_3\ =$ zz の $3$ 通りありますが、文字列 z は答えに $1$ 回だけ寄与することに注意してください。