该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

假设有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。