/ Vijos / 题库 /

String

String

描述

假设有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
1789
难度
6
分类
其他 | 数学 点击显示
标签
(无)
递交数
162
已通过
42
通过率
26%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库

加油!向青春

在下列比赛中:

Vijos2012年11月份月赛