String

String

测试数据来自 system/1789

描述

假设有M个字母,问由这些字母可以组成多少个满足以下条件的长度为N的串:该串的任意长度为K的子串是一个回文串。答案可能很大,只需输出对10^9+7取模的结果。

回文串是指从左往右和从右往左读起来一样。例如:aba, abba

格式

输入格式

读入三个正整数:N,M,K。

输出格式

输出一个整数,表示满足条件的串的个数对10^9+7取模的结果。

样例1

样例输入1

5 2 4

样例输出1

2

限制

每个测试点1s。

提示

对于30%的测试数据,N,M<=5。

对于100%的测试数据,N,M,K<=2000。

信息

ID
1831
难度
(无)
分类
其他 | 数学 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者