#include <bits/stdc++.h>
#define int long long
template <int m>
class ModInt {
    int raw_;
public:
    ModInt() : raw_(0) {}
    ModInt(const auto &v) : raw_(v % m) {}
    using i64 = int64_t;
    using mint = ModInt;
    mint &operator+=(const mint &rhs) {
        raw_ = (raw_ + rhs.raw_) % m;
        return *this;
    }
    mint &operator-=(const mint &rhs) {
        raw_ = (raw_ - rhs.raw_) % m;
        return *this;
    }
    mint &operator*=(const mint &rhs) {
        raw_ = (i64)raw_ * rhs.raw_ % m;
        return *this;
    }
    mint &operator/=(const mint &rhs) {
        raw_ = (i64)raw_ * qpow(rhs.raw_, m - 2) % m;
        return *this;
    }
    friend mint operator+(const mint &lhs, const mint &rhs) {
        return mint{lhs} += rhs;
    }
    friend mint operator-(const mint &lhs, const mint &rhs) {
        return mint{lhs} -= rhs;
    }
    friend mint operator*(const mint &lhs, const mint &rhs) {
        return mint{lhs} *= rhs;
    }
    friend mint operator/(const mint &lhs, const mint &rhs) {
        return mint{lhs} /= rhs;
    }

    int value() const {
        return (raw_ + m) % m;
    }
    static constexpr int qpow(int a, int b) {
        int res = 1;
        while (b) {
            if (b & 1) {
                res = (i64)res * a % m;
            }
            a = (i64)a * a % m, b >>= 1;
        }
        return res;
    }
};

using mint = ModInt<static_cast<int>(1e9 + 7)>;
constexpr int MAXM = 2e3 + 19;
constexpr int MAXN = 1e6 + 19;

std::map<int, mint> fact, ifact;
void init_fact(int k) {
    const int N = 5090, L = std::max(k - N, 0LL);
    const int LIM = 20000;

    if (k <= LIM) {
        fact[0] = 1;
        for (int i = 1; i <= LIM; ++i) {
            fact[i] = fact[i - 1] * i;
        }
        ifact[LIM] = 1 / fact[LIM];
        for (int i = LIM - 1; i >= 0; --i) {
            ifact[i] = ifact[i + 1] * (i + 1);
        }
        return;
    }
    
    ifact[k] = 19;
    for (int i = k - 1; i >= L; --i) {
        ifact[i] = ifact[i + 1] * (i + 1);
    }
    fact[L] = 1 / ifact[L];
    for (int i = L + 1; i <= k; ++i) {
        fact[i] = fact[i - 1] * i;
    }

    fact[0] = 1;
    for (int i = 1; i <= N; ++i) {
        fact[i] = fact[i - 1] * i;
    }
    ifact[N] = 1 / fact[N];
    for (int i = N - 1; i >= 0; --i) {
        ifact[i] = ifact[i + 1] * (i + 1);
    }
}
mint binom(int n, int m) {
    return fact[n] * ifact[n - m] * ifact[m];
}
mint A(int n, int m) {
    return fact[n] * ifact[n - m];
}

mint L(int m, int k) {
    mint res = 0;
    mint C = 1;
    for (int occ2 = 0; occ2 * 2 <= m; ++occ2) {
        if (occ2 <= k && m - occ2 * 2 <= k - occ2) {
            mint v = binom(k, occ2) * A(k - occ2, m - occ2 * 2);
            //// mint v=binom(k,occ2)*binom(k-occ2,m-occ2*2)*fact[m]/mint::qpow(2,occ2);
            res += v * C;
        }

        if (2 <= m - occ2 * 2) {
            C *= binom(m - occ2 * 2, 2);
        }
    }
    return res;
}

int n, m, k;
mint occ[MAXN];
mint V[MAXM];
void init_occ() {
    for (int i = 1; i <= n; ++i) {
        occ[i] = (n - i + 1) * mint::qpow(k, n - i);
    }
}
void init_V() {
    mint f = 1;
    for (int i = 1; i * 2 <= m; ++i) {
        f *= (k - i + 1);
        V[i] = f * L(m - i * 2, k - i);
    }

    V[0] = L(m, k);
    for (int i = 1; i * 2 <= m; ++i) {
        V[0] -= V[i];
    }
}

mint g[MAXN], f[MAXN];

int32_t main() {
    std::cin >> n >> m >> k;

    init_fact(k);
    init_occ();
    init_V();

    // std::cout << "PRE DONE\n";

    int lim = 1;
    
    g[1] += occ[m] * V[0];
    for (int i = 1; m * i - (i - 1) * (m / 2) <= n; ++i) {
        lim = i;
        for (int a = m / 2; a >= 1 && m * i - (i - 1) * a <= n; --a) {
            g[i] += occ[m * i - (i - 1) * a] * V[a];
        }
    }

    // std::cout << "g_1 = " << g[1].value() << '\n';

    mint ans = 0;
    for (int i = 1; i <= lim; ++i) {
        f[i] = (g[i] - g[i + 1]) - (g[i + 1] - g[i + 2]);
        ans += f[i] * ((i + 1) / 2);
        // std::cout << f[i].value() << '\n';
    }
    std::cout << ans.value() << '\n';
}