#P18500. Enumerating Substrings
Enumerating Substrings
Enumerating Substrings
有一个大小为 的字母表。对于该字母表上的一个字符串 (文本)和一个字符串 (模式),定义 为:从 中选取若干个两两不重叠、且都等于 的子串时,最多可以选取的子串个数。
如果字符串 中每种字母出现的次数均不超过 2 次,则称 是漂亮的。
考虑所有长度为 的文本 ,以及所有长度为 的漂亮模式 ,求它们的 之和。由于结果可能很大,输出其对 取模后的值。
文本 和模式 都使用这个同一个大小为 的字母表。题目只要求 漂亮; 没有每种字母次数的限制。子串不能重叠,但相邻的两个子串可以紧贴。
输入格式
输入只有一行,包含三个整数 ,分别表示文本长度、模式长度、字母表大小。
- ;
- ,并且 ;
- 。
本题输入只有一组数据。
输出格式
输出一行一个整数,表示所有长度为 的文本 和长度为 的漂亮模式 的 总和,对 取模。
原样例 1
4 2 3
228
原样例 2
999999 1999 12345678
52352722