Score : $500$ points

## 问题描述

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

> 将 $T$ 的两个副本拼接而成的字符串 $TT$ 是 $S$ 的子序列（不一定是连续的）。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 12:24:59