以防万一有人错过了:今年冬天恩沃茨克非常冷!天气太冷了,让人产生一些奇怪的想法。例如,假设基于大小为 m 的字母表,长度恰好为 n 的字符串。它的任何长度等于 k 的子串都是回文。存在多少个这样的字符串?你的任务是找到它们的数量模 1000000007 (109 + 7)。小心一点,不要错过一两根绳子!
让我们提醒您,如果一个字符串可以从左到右和从右到左以相同的方式读取,那么它就是回文。
输入
第一行也是唯一一行包含三个整数:n、m 和 k (1 ≤ n、m、k ≤ 2000)。
输出
打印单个整数 — 所描述类型的字符串数量以 1000000007 (109 + 7) 为模。
示例
输入 #1
1 1 1
输出 #1
1
输入 #2
5 2 4
输出 #2
2
注意
在第一个示例中,只有一个字符串有效:“a”(让我们将字母表中唯一的字母表示为“a”)。
在第二个示例中(如果我们将字母表字母表示为“a”和“b”),以下字符串有效:“aaaaa”和“bbbbb”。