CF150B.Quantity of Strings

Just in case somebody missed it: this winter is totally cold in Nvodsk! It is so cold that one gets funny thoughts. For example, let's say there are strings with the length exactly n, based on the alphabet of size m. Any its substring with length equal to k is a palindrome. How many such strings exist? Your task is to find their quantity modulo 1000000007 (109 + 7). Be careful and don't miss a string or two!

Let us remind you that a string is a palindrome if it can be read the same way in either direction, from the left to the right and from the right to the left.

以防有人没注意到：今年冬天，Nvodsk 的天气异常寒冷！寒冷到让人产生一些有趣的想法。例如，考虑所有长度恰好为 $n$、基于大小为 $m$ 的字母表构成的字符串。要求该字符串中任意长度为 $k$ 的子串均为回文串。问这样的字符串一共有多少个？你的任务是求出其数量对 $1000000007$（即 $10^9 + 7$）取模的结果。请务必小心，不要遗漏任何一个字符串！

需要提醒的是：若一个字符串从左向右读与从右向左读完全相同，则称其为回文串。

The first and only line contains three integers: n, m and k (1 ≤ n, m, k ≤ 2000).

第一行且唯一一行包含三个整数：$n$、$m$ 和 $k$（$1 ≤ n, m, k ≤ 2000$）。

Print a single integer — the number of strings of the described type modulo 1000000007 (109 + 7).

输出一个整数——满足上述条件的字符串数量对 1000000007（即 $10^9 + 7$）取模的结果。

In the first sample only one string is valid: "a" (let's denote the only letter of our alphabet as "a").

In the second sample (if we denote the alphabet letters as "a" and "b") the following strings are valid: "aaaaa" and "bbbbb".

在第一个样例中，仅有一个字符串是合法的：“a”（我们用“a”表示字母表中的唯一字母）。

在第二个样例中（若用“a”和“b”表示字母表中的字母），以下字符串是合法的：“aaaaa”和“bbbbb”。