String
描述
假设有M个字母,问由这些字母可以组成多少个满足以下条件的长度为N的串:该串的任意长度为K的子串是一个回文串。答案可能很大,只需输出对10^9+7取模的结果。
回文串是指从左往右和从右往左读起来一样。例如:aba, abba
格式
输入格式
读入三个正整数:N,M,K。
输出格式
输出一个整数,表示满足条件的串的个数对10^9+7取模的结果。
样例1
样例输入1
样例输出1
限制
每个测试点1s。
提示
对于30%的测试数据,N,M<=5。
对于100%的测试数据,N,M,K<=2000。