/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
英小文字のみからなる文字列 S が与えられます。 下記の条件を満たす空でない文字列 T の個数を 998244353 で割ったあまりを出力してください。
T を 2 つ連結して得られる文字列 TT が、S に（連続とは限らない）部分列として含まれる。
制約
- S は英小文字のみからなる長さ 1 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
ababbaba
出力例 1
8
問題文中の条件を満たす文字列 T は、a 、aa 、ab 、aba 、b 、ba 、bab 、bb の 8 個です。
入力例 2
zzz
出力例 2
1
問題文中の条件を満たす文字列 T は、z のみです。
S = S_1S_2S_3 = zzz から、文字列 zz を部分列として得る方法は、
S_1S_2 = zz 、S_1S_3 = zz 、S_2S_3 = zz の 3 通りありますが、文字列 z は答えに 1 回だけ寄与することに注意してください。
入力例 3
ppppqqppqqqpqpqppqpqqqqpppqppq
出力例 3
580
Score : 500 points
Problem Statement
You are given a string S consisting of lowercase English letters. Print the number of non-empty strings T that satisfy the following condition, modulo 998244353.
The concatenation TT of two copies of T is a subsequence of S (not necessarily contiguous).
Constraints
- S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
ababbaba
Sample Output 1
8
The eight strings satisfying the condition are a, aa, ab, aba, b, ba, bab, and bb.
Sample Input 2
zzz
Sample Output 2
1
The only string satisfying the condition is z.
Note that this string contributes to the answer just once, although there are three ways to extract the subsequence zz from S = S_1S_2S_3 = zzz: S_1S_2 = zz, S_1S_3 = zz, and S_2S_3 = zz.
Sample Input 3
ppppqqppqqqpqpqppqpqqqqpppqppq
Sample Output 3
580