#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())

using namespace std;

#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
			.time_since_epoch().count());
#endif

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

using ll = long long;
using ld = double;

using uint = unsigned int;
using ull = unsigned long long;
template <uint MD> struct ModInt {
    using M = ModInt;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint((ull)v * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    bool operator!=(const M& r) const { return v != r.v; }
    M inv() const;
    friend istream& operator>>(istream& is, M& r) { ll x; is >> x; r = M(x); return is; }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};

template<uint MD>
ModInt<MD> pow(ModInt<MD> x, ll n) {
    ModInt<MD> r = 1;
    while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
    }
    return r;
}

template<uint MD>
ModInt<MD> ModInt<MD>::inv() const { return pow(*this, MD - 2); }

using Mint = ModInt<int(1e9) + 7>;
// using Mint = double;


const int maxn = 1e6 + 100, inf = 1e9 + 100;

Mint pwk[maxn], pw2[maxn];

Mint ak[maxn], f[maxn], of[maxn];

void solve() {
    int n, m, K;
    cin >> n >> m >> K;
    pwk[0] = 1;
    pw2[0] = 1;
    ak[0] = 1;
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw2[i] = pw2[i - 1] * 2;
        pwk[i] = pwk[i - 1] * K;
        f[i] = f[i - 1] * i;
        ak[i] = ak[i - 1] * (K - i + 1);
    }
    of[n] = Mint(1) / f[n];
    for (int i = n - 1; i >= 0; i--) {
        of[i] = of[i + 1] * (i + 1);
    }
    auto choose = [&](int k, int l) -> Mint {
        if (k < 0)
            return 0;
//        Mint z = 1;
//        for (int i = 0; i < l; i++)
//            z *= (k - i);
//        return z;
        // (k .. k-l+1)
        return ak[K - k + l] / ak[K - k];
    };
    auto get_ms = [&](int k, int l) -> Mint {
        if (k < 0)
            return 0;
        Mint w = 0;
        for (int s = 0; 2 * s <= l; s++) {
            w += f[l] / pw2[s] * choose(k, l - s) / f[l - s] * f[l - s] / f[s] / f[l - 2 * s];
        }
        return w;
    };
    auto fi = [&](int k, int j) -> Mint {
        int kpw = n - ((j + 1) * (m - k) + k);
        if (kpw < 0)
            return 0;
        int le = (m - k) * j;
        int re = n - m;
        return pwk[kpw] * max(0, re - le + 1);
    };
    Mint ans = 0;
    Mint totm = get_ms(K, m);
    for (int k = 1; 2 * k <= m; k++) {
        Mint cur_ms = choose(K, k) * get_ms(K - k, m - 2 * k);
        totm -= cur_ms;
        for (int j = 0; (2 * j + 1) * (m - k) + k <= n; j++) {
            ans += cur_ms * (fi(k, 2 * j) - fi(k, 2 * j + 1));
        }
    }
    {
        // k = 0
        ans += Mint(n - m + 1) * totm * pwk[n - m];
    }
    cout << ans << '\n';
}

int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
//    freopen("../a.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    cout.precision(20);
    solve();
    cerr << "\n\nConsumed " << TIME << endl;
}