#include <bits/stdc++.h>

const int mod = 1e9 + 7;
using ll = long long;

int norm(int x) {
    if (x < 0) {
        x += mod;
    }
    if (x >= mod) {
        x -= mod;
    }
    return x;
}
 
template<class T>
T power(T a, int b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
 
struct mint {
    int x;
    mint(int x = 0) : x(norm(x)) {}
    int val() const {
        return x;
    }
    mint operator-() const {
        return mint(norm(mod - x));
    }
    mint inv() const {
        assert(x != 0);
        return power(*this, mod - 2);
    }
    mint &operator*=(const mint &rhs) {
        x = ll(x) * rhs.x % mod;
        return *this;
    }
    mint &operator+=(const mint &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    mint &operator-=(const mint &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    mint &operator/=(const mint &rhs) {
        return *this *= rhs.inv();
    }
    friend mint operator*(const mint &lhs, const mint &rhs) {
        mint res = lhs;
        res *= rhs;
        return res;
    }
    friend mint operator+(const mint &lhs, const mint &rhs) {
        mint res = lhs;
        res += rhs;
        return res;
    }
    friend mint operator-(const mint &lhs, const mint &rhs) {
        mint res = lhs;
        res -= rhs;
        return res;
    }
    friend mint operator/(const mint &lhs, const mint &rhs) {
        mint res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, mint &a) {
       ll v;
       is >> v;
       a = mint(v);
       return is;
   }
   friend std::ostream &operator<<(std::ostream &os, const mint &a) {
       return os << a.val();
   }
};


struct Comb {
    int n;
    std::vector<mint> _fac;
    std::vector<mint> _invfac;
    std::vector<mint> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    mint fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    mint invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    mint inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    mint binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n, m, k;
    std::cin >> n >> m >> k;
    mint res = 0;
    std::vector<mint> pw(n + 1);
    pw[0] = 1;
    for (int i = 1; i <= n; i += 1) {
        pw[i] = pw[i - 1] * mint(k);
    }
    std::vector f(m + 1, std::vector<mint>(m + 1));
    f[0][0] = 1;
    for (int i = 1; i <= m; i += 1) {
        for (int j = 0; j <= m; j += 1) {
            if (j + 1 <= m) {
                f[i][j + 1] += f[i - 1][j];
            }
            if (j + 2 <= m) {
                f[i][j + 2] += f[i - 1][j] * comb.invfac(2);
            } 
        }
    }

    {
        mint tmp = 1;
        for (int c = 0; c <= m; c += 1) {
            res += f[c][m] * comb.fac(m) * tmp * mint(n - m + 1) * power(mint(k), n - m);
            tmp = tmp * (k - c) * comb.inv(c + 1);
        }
    }
    
    {
        mint tmp = 1;
        std::vector<mint> dp(m);
        for (int i = 1; i <= m; i += 1) {
            tmp *= k - i + 1;
            if (i + i <= m) {
                mint coef = 1;
                for (int c = 0; c <= m - 2 * i; c += 1) {
                    // std::cerr << i << " " << c << " " << f[c][m - 2 * i] * comb.fac(m - 2 * i) << " " << tmp << " " << coef << "\n";
                    dp[i] += f[c][m - 2 * i] * comb.fac(m - 2 * i) * tmp * coef;
                    coef = coef * (k - i - c) * comb.inv(c + 1);
                }
            }
            // else {
            //     int x = i - (m - i + 1) + 1;
            //     if (x + x >= i) {
            //         mint coef = 1;
            //         for (int c = 0; c <= i - 2 * x; c += 1) {
            //             dp[2 * m - x] += f[c][m - 2 * x] * comb.fac(m - 2 * x) * tmp;
            //             coef = coef * (k - x - c) * comb.inv(c + 1);
            //         }
            //     }
            // }
            // for (int len = 0; len <= 2 * m; len += 1) {
            //     res -= dp[len] * (n - len + 1) * power(mint(k), n - len); 
            // }
        }
        for (int len = 0; len < m; len += 1) {
            int sign = 0;
            for (int x = 2; x * m - (x - 1) * len <= n; x += 1) {
                int c = x * m - (x - 1) * len;
                if (sign) res += dp[len] * (n - c + 1) * pw[n - c]; 
                else res -= dp[len] * (n - c + 1) * pw[n - c]; 
                sign ^= 1;
            }
        }
    }
    std::cout << res << "\n";
    return 0;
}