#P17913. Pen Pineapple Apple Pen

Pen Pineapple Apple Pen

题目描述

给定长度为 nn 的小写英文字母串 SS。请统计满足下列要求的八元组

(i1,j1,i2,j2,i3,j3,i4,j4)(i_1,j_1,i_2,j_2,i_3,j_3,i_4,j_4)

的数量:

$$1\le i_1\le j_1<i_2\le j_2<i_3\le j_3<i_4\le j_4\le n.$$

它们依次指定四个非空、互不重叠的子串。相邻子串之间允许有未选中的字符,也允许紧邻。

  • 第一个子串 S[i1..j1]S[i_1..j_1] 与第四个子串 S[i4..j4]S[i_4..j_4] 完全相同。
  • 第三个子串 S[i3..j3]S[i_3..j_3] 是第二个子串 S[i2..j2]S[i_2..j_2] 的严格后缀:两者结尾部分相同,且第三个子串的长度严格小于第二个。

只要八个下标中有一个不同,就算不同方案。输出方案数模 998244353998244353 的结果。

输入格式

输入一行字符串 SS。每个文件只有一组数据。

输出格式

输出一个整数,表示方案数模 998244353998244353。

数据范围

1≤∣S∣≤50001\le|S|\le5000,所有字符均为小写英文字母。

样例 1

ppaap
1

样例 2

ppapppap
16

样例 3

penpineappleapplepen
1502