#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int MOD = 1e9 + 7;

int add(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}

int sub(int a, int b) {
    return a >= b ? a - b : a + MOD - b;
}

int mul(int a, int b) {
    return (1ll * a * b) % MOD;
}

int pw(int x, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            x = mul(x, x);
            n /= 2;
        } else {
            res = mul(res, x);
            --n;
        }
    }
    return res;
}

const int MAXF = 1e5 + 100;
int fact[MAXF], invf[MAXF];

int pw2[MAXF];

int C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return mul(fact[n], mul(invf[k], invf[n - k]));
}

int inv(int x) {
    return mul(invf[x], fact[x - 1]);
}

int get2(int m, int k) {
    if (k < 0) return 0;
    if (m == 0) return 1;
    int c = 1;
    int ans = 0;
    for (int t = 1; t <= m; ++t) {
        c = mul(c, k - t + 1);
        c = mul(c, inv(t));
        int cur = mul(c, mul(C(t, m - t), mul(fact[m], pw2[m - t])));
        ans = add(ans, cur);
    }
    return ans;
}

const int MAXM = 2e3 + 100;
int cnt[MAXM];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    fact[0] = 1;
    for (int i = 1; i < MAXF; ++i) {
        fact[i] = mul(fact[i - 1], i);
    }
    invf[MAXF - 1] = pw(fact[MAXF - 1], MOD - 2);
    for (int i = MAXF - 1; i > 0; --i) {
        invf[i - 1] = mul(invf[i], i);
    }

    pw2[0] = 1;
    for (int i = 1; i < MAXF; ++i) {
        pw2[i] = mul(pw2[i - 1], (MOD + 1) / 2);
    }

    int n, m, k;
    cin >> n >> m >> k;
    int c = 1;
    for (int l = 0; l * 2 <= m; ++l) {
        cnt[m - l] = mul(get2(m - 2 * l, k - l), c);
        c = mul(c, k - l);
        /// c = mul(c, inv(l + 1));
        /// cerr << l << ": " << cnt[m - l] << endl;
    }
    int total = 0;
    for (int i = 0; i < m; ++i) {
        cnt[m] = sub(cnt[m], cnt[i]);
        total = add(total, cnt[i]);
    }

    int ans = mul(cnt[m], mul(pw(k, n - m), n - m + 1));

    /// cerr << ans << endl;

    vector<int> f(n + 1);
    for (int l = 1; l < m; ++l) {
        for (int i = l; i <= n; i += l) {
            if ((i / l) % 2 == 1) {
                f[i] = add(f[i], cnt[l]);
            } else {
                f[i] = sub(f[i], cnt[l]);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        f[i] = add(f[i], mul(f[i - 1], k));
        /// cerr << i << ": " << f[i] << endl;
    }
    for (int i = m; i <= n; ++i) {
        int cur = sub(mul(pw(k, i - m), total), f[i - m]);
        /// cerr << i << endl;
        /// cerr << pw(k, i - m) << " " << f[i - m] << endl;
        /// cerr << i << ": " << cur << endl;
        ans = add(ans, mul(cur, pw(k, n - i)));
    }
    cout << ans << "\n";
    
    return 0;
}