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 (10<sup class="upper-index">9</sup> + 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.
The first and only line contains three integers: *n*, *m* and *k* (1 ≤ *n*, *m*, *k* ≤ 2000).
1 1 1
1
5 2 4
2
7 4 20
16384
8 13 9
815730721
10 23 9
529
10 25 8
25
997 1752 1000
184834849
784 1 1999
1
341 9 342
320920086
777 1 777
1
542 13 542
490685740
1501 893 1501
889854713
1321 95 2
95
2000 1000 3
1000000
1769 849 1000
849
1000 2 1
688423210
345 1777 1
756253754
1999 2000 2000
675798323
1984 1847 1992
345702953
2000 2000 2000
321179016
1451 239 1451
968856942
2000 2000 1
596636543
1230 987 1
890209975
1764 305 843
93025
1999 98 132
98
2000 2 10
2
2000 1999 1999
3996001
1678 1999 1234
1999
7 10 7
10000
15 1 15
1
2000 2000 1000
2000
1 2000 2000
2000
10 10 90
999999937
100 100 1
424090053
6 6 6
216
10 10 1
999999937
100 10 100
319300014
5 4 5
64
5 2 5
8
1000 1000 1000
850431726
5 5 1
3125
1000 1000 1
524700271
4 256 1
294967268
5 5 5
125
10 10 10
100000
100 100 100
226732710
5 2 1
32
4 4 4
16
15 5 1
517577915
1000 2 1001
688423210
100 7 3
49
8 2 8
16
200 200 200
104842676
4 4 1
256
1999 1999 1999
21610777
17 5 1
939447791
100 5 1
146981449
10 5 1
9765625
11 2 11
64
100 1000 1
327648028
3 1000 3
1000000
3 3 3
9
3 5 3
25
20 3 3
9
10 2 1
1024
7 2 7
16
13 9 1
865810542
11 2 5
4
13 13 13
62748517
239 123 239
221051222
import sys
import math
import collections
from heapq import heappush, heappop
input = sys.stdin.readline
 
ints = lambda: list(map(int, input().split()))

class UnionFind:
    def __init__(self, size):
        self.link = [i for i in range(size)]
        self.size = [1 for _ in range(size)]

    def find(self, a):
        while self.link[a] != a:
            a = self.link[a]
        return a

    def same(self, a, b):
        return self.find(a) == self.find(b)

    def join(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if (self.size[a] > self.size[b]):
            a, b = b, a
        self.link[a] = b
        self.size[b] += self.size[a]
        return b


n, m, k = ints()
dsu = UnionFind(n)
for i in range(n // 2):
    dsu.join(i, n - i - 1)

for i in range(n - k + 1):
    for j in range(i, i + (k // 2)):
        if not dsu.same(j, i + k - j - 1):
            dsu.join(j, i + k - j - 1)

ans = 1
for i in range(n):
    if dsu.link[i] == i:
        ans *= m
        ans = ans % (10 ** 9 + 7)
print(ans)