#include <bits/stdc++.h>
using namespace std;
long long int mod = 1e9 + 7;
bool isPrime(long long int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
long long int power(long long int x, long long int y, long long int p) {
  long long int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long int mI(long long int x) { return power(x, mod - 2, mod); }
long long int gcd(long long int a, long long int b, long long int &x,
                  long long int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long int x1, y1;
  long long int gcd_c = gcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - y1 * (a / b);
  return gcd_c;
}
void make_set(int n, vector<int> &par, vector<int> &rank) {
  for (int i = 1; i <= n; i++) {
    par[i] = i;
    rank[i] = 0;
  }
}
int find_set(int a, vector<int> &par) {
  if (par[a] == a)
    return a;
  else
    return par[a] = find_set(par[a], par);
}
void union_set(int a, int b, vector<int> &par, vector<int> &rank) {
  a = find_set(a, par);
  b = find_set(b, par);
  if (a == b) return;
  if (rank[b] > rank[a]) swap(a, b);
  par[b] = a;
  if (rank[a] == rank[b]) rank[a]++;
}
void solve() {
  long long int n, m, k, i, j, ans, l;
  cin >> n >> m >> k;
  if (k == 1 || k > n) {
    ans = 1;
    for (i = 1; i <= n; i++) {
      ans = (ans * m) % mod;
    }
  } else if (k == n) {
    ans = 1;
    for (i = 1; i <= (n + 1) / 2; i++) {
      ans = (ans * m) % mod;
    }
  } else if (k % 2 == 0) {
    ans = m;
  } else if (k % 2 != 0) {
    ans = m;
    if (m > 1) {
      ans = (ans + m * (m - 1)) % mod;
    }
  }
  cout << ans << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int t = 1;
  while (t--) {
    solve();
  }
}

### Prompt

Create a solution in Cpp for the following problem:

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.

Input

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

Output

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

Examples

Input

1 1 1


Output

1


Input

5 2 4


Output

2

Note

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".

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long int mod = 1e9 + 7;
bool isPrime(long long int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
long long int power(long long int x, long long int y, long long int p) {
  long long int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long int mI(long long int x) { return power(x, mod - 2, mod); }
long long int gcd(long long int a, long long int b, long long int &x,
                  long long int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long int x1, y1;
  long long int gcd_c = gcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - y1 * (a / b);
  return gcd_c;
}
void make_set(int n, vector<int> &par, vector<int> &rank) {
  for (int i = 1; i <= n; i++) {
    par[i] = i;
    rank[i] = 0;
  }
}
int find_set(int a, vector<int> &par) {
  if (par[a] == a)
    return a;
  else
    return par[a] = find_set(par[a], par);
}
void union_set(int a, int b, vector<int> &par, vector<int> &rank) {
  a = find_set(a, par);
  b = find_set(b, par);
  if (a == b) return;
  if (rank[b] > rank[a]) swap(a, b);
  par[b] = a;
  if (rank[a] == rank[b]) rank[a]++;
}
void solve() {
  long long int n, m, k, i, j, ans, l;
  cin >> n >> m >> k;
  if (k == 1 || k > n) {
    ans = 1;
    for (i = 1; i <= n; i++) {
      ans = (ans * m) % mod;
    }
  } else if (k == n) {
    ans = 1;
    for (i = 1; i <= (n + 1) / 2; i++) {
      ans = (ans * m) % mod;
    }
  } else if (k % 2 == 0) {
    ans = m;
  } else if (k % 2 != 0) {
    ans = m;
    if (m > 1) {
      ans = (ans + m * (m - 1)) % mod;
    }
  }
  cout << ans << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int t = 1;
  while (t--) {
    solve();
  }
}

```