#P17913. Pen Pineapple Apple Pen
Pen Pineapple Apple Pen
题目描述
给定长度为 的小写英文字母串 。请统计满足下列要求的八元组
的数量:
$$1\le i_1\le j_1<i_2\le j_2<i_3\le j_3<i_4\le j_4\le n.$$它们依次指定四个非空、互不重叠的子串。相邻子串之间允许有未选中的字符,也允许紧邻。
- 第一个子串 与第四个子串 完全相同。
- 第三个子串 是第二个子串 的严格后缀:两者结尾部分相同,且第三个子串的长度严格小于第二个。
只要八个下标中有一个不同,就算不同方案。输出方案数模 的结果。
输入格式
输入一行字符串 。每个文件只有一组数据。
输出格式
输出一个整数,表示方案数模 。
数据范围
,所有字符均为小写英文字母。
样例 1
ppaap
1
样例 2
ppapppap
16
样例 3
penpineappleapplepen
1502