#P18500. Enumerating Substrings

Enumerating Substrings

Enumerating Substrings

有一个大小为 kk 的字母表。对于该字母表上的一个字符串 SS(文本)和一个字符串 PP(模式),定义 F(S,P)F(S,P) 为:从 SS 中选取若干个两两不重叠、且都等于 PP 的子串时,最多可以选取的子串个数。

如果字符串 QQ 中每种字母出现的次数均不超过 2 次,则称 QQ 是漂亮的。

考虑所有长度为 nn 的文本 SS,以及所有长度为 mm 的漂亮模式 PP,求它们的 F(S,P)F(S,P) 之和。由于结果可能很大,输出其对 109+710^9+7 取模后的值。

文本 SS 和模式 PP 都使用这个同一个大小为 kk 的字母表。题目只要求 PP 漂亮;SS 没有每种字母次数的限制。子串不能重叠,但相邻的两个子串可以紧贴。

输入格式

输入只有一行,包含三个整数 n,m,kn,m,k,分别表示文本长度、模式长度、字母表大小。

  • 1≤n≤1061\le n\le 10^6;
  • 1≤m≤20001\le m\le 2000,并且 m≤nm\le n;
  • 1≤k≤1091\le k\le 10^9。

本题输入只有一组数据。

输出格式

输出一行一个整数,表示所有长度为 nn 的文本 SS 和长度为 mm 的漂亮模式 PP 的 F(S,P)F(S,P) 总和,对 109+710^9+7 取模。

原样例 1

4 2 3
228

原样例 2

999999 1999 12345678
52352722