/*
1. min{F(i, j), F(j, k)} <= F(i, k)：考虑对于任意一组大小小于 min{F(i, j), F(j, k)} 的割，都会保留一条 i -> j，j -> k 的通路。
2. 将所有流至少为 1 的边，分别讨论连通块；将所有流至少为 2 的边，分别讨论连通块，这些连通块外部连边构成连。
3. 对所有流至少为 3 的边，构成团，若团大小：
    - 至少为 4 的偶数：连成环之后，相对的两个点连边。
    - 至少为 4 的奇数：除去最后一个点之外连成环之后，与最后一个点连边。
    - 上面两种其中一个点作为代表连到环内。
    - 2：
        * 只有一个这样的团，这两个点不能相邻，之间额外连边。
        * 若连通块内点数不超过 3，无解。
        * 存在更多这样的团无解。
    - 3：
        * 只有一个这样的团，这三个点之间额外连任意两条边，相连边的两个点不能相邻。
        * 连通块的点个数不超过 4，无解。
4. 按团的数量连外部边：
    - 1：不用管。
    - 2：若大小都为 1，无解；否则将其中一个不为 1 的团中任意两个点向另一个团的点连边。
    - 3：否则可以连成环。
5. 听说上面这样搞出来有反例的，但是不知道是什么。
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e6 + 5, P = 1e9 + 7;

int n, m, k;
LL fact[N], invf[N], ck[N], s2[N], pk[N];
LL f[N];

inline LL ksm(LL a, LL n)
{
    LL res = 1;
    while(n)
    {
        if(n & 1) res = res * a % P;
        a = a * a % P;
        n >>= 1;
    }
    return res;
}
inline void Init(int n)
{
    fact[0] = 1;
    for(int i = 1; i <= n; i ++ ) fact[i] = fact[i - 1] * i % P;
    invf[n] = ksm(fact[n], P - 2);
    for(int i = n; i >= 1; i -- ) invf[i - 1] = invf[i] * i % P;
    ck[0] = 1;
    for(int i = 1; i <= n; i ++ ) ck[i] = ck[i - 1] * (k - i + 1) % P;
    s2[0] = 1;
    for(int i = 1; i <= n / 2; i ++ ) s2[i] = s2[i - 1] * (i * 2 - 1) % P;
    for(int i = 1; i <= n / 2; i ++ ) s2[i] = s2[i] * invf[i * 2] % P;
    pk[0] = 1;
    for(int i = 1; i <= n; i ++ ) pk[i] = pk[i - 1] * k % P;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    Init(n);
    LL s0 = 0;
    for(int i = m / 2; i >= 0; i -- )
    {
        LL s = 0;
        for(int j = 0; j <= m / 2 - i; j ++ )
            s = (s + ck[m - i - j] * invf[m - i * 2 - j * 2] % P * s2[j]) % P;
        s = s * fact[m - i * 2] % P;
        if(i == 0)
        {
            s -= s0;
            f[m] += s;
        }
        else
        {
            (s0 += s) >= P && (s0 -= P);
            for(int j = m, k = 1; j <= n; j += m - i, k = -k) f[j] += s * k;
        }
    }
    
    LL ans = 0;
    for(int i = m; i <= n; i ++ ) ans = (ans + (f[i] % P + P) * (n - i + 1) % P * pk[n - i]) % P;
    printf("%lld\n", ans);
    return 0;
}