102995: [Atcoder]ABC299 F - Square Subsequence

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

问题描述

给你一个由小写英文字母组成的字符串$S$。打印满足以下条件的不同非空字符串$T$的数量（模998244353）。

两个$T$的复制$TT$是$S$的子序列（不一定连续）。

限制条件

• $S$是一个长度在1到100之间的由小写英文字母组成的字符串。

输入

输入数据通过标准输入给出如下格式：

$S$

输出

打印答案。

样例输入1

ababbaba

样例输出1

8

满足条件的8个字符串是 a, aa, ab, aba, b, ba, bab, 和 bb。

样例输入2

zzz

样例输出2

1

满足条件的唯一字符串是z。注意，虽然有三种方法从$S = S_1S_2S_3 = $ zzz中提取子序列zz：$S_1S_2 = $ zz, $S_1S_3 = $ zz, 和 $S_2S_3 = $ zz，但这字符串只贡献一次答案。

样例输入3

ppppqqppqqqpqpqppqpqqqqpppqppq

样例输出3

580