← 返回题目列表

AtCoder · abc299_f

I. 平方子序列

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

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

连接 TT 两份 T 是以下序列的子序列 S (不一定是连续的)。

约束

  • S 是由小写英文字母组成的字符串,长度介于 1 和 100,包括在内。

输入

输入由标准输入按以下格式给出:

S

输出

打印答案。


示例输入 1

ababbaba

示例输出 1

8

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


示例输入 2

zzz

示例输出 2

1

唯一满足条件的字符串是 z。 请注意,尽管有三种方法可以提取子序列,但该字符串仅对答案做出一次贡献 zz 来自 S = S_1S_2S_3 = zzz: S_1S_2 = zz, S_1S_3 = zz,和 S_2S_3 = zz.


示例输入 3

ppppqqppqqqpqpqppqpqqqqpppqppq

示例输出 3

580