#include <bits/stdc++.h>

 typedef long long LL;

 const int N = , MO = ;

 int n, k, d;

 inline int qpow(int a, int b) {

     int ans();

     while(b) {

         if(b & ) {

             ans = (LL)ans * a % MO;

         }

         a = (LL)a * a % MO;

         b = b >> ;

     }

     return ans;

 }

 namespace DP {

     int f[][], C[][];

     inline void solve() {

         f[][] = ;

         for(int i = ; i <= ; i++) {

             C[i][] = C[i][i] = ;

             for(int j = ; j < i; j++) {

                 C[i][j] = (C[i - ][j] + C[i - ][j - ]) % MO;

             }

         }

         for(int i = ; i < k; i++) {

             for(int j = ; j <= n; j++) {

                 for(int p = ; j + p <= n; p += d) {

                     (f[i + ][j + p] += (LL)f[i][j] * C[n - j][p] % MO) %= MO;

                 }

             }

         }

         printf("%d\n", f[k][n]);

         return;

     }

 }

 namespace D2 {

     int fac[N], inv[N], invn[N];

     inline int C(int n, int m) {

         if(n <  || m <  || n < m) return ;

         return (LL)fac[n] * invn[m] % MO * invn[n - m] % MO;

     }

     inline void solve() {

         fac[] = inv[] = invn[] = ;

         fac[] = inv[] = invn[] = ;

         for(int i = ; i <= k; i++) {

             fac[i] = (LL)fac[i - ] * i % MO;

             inv[i] = (LL)inv[MO % i] * (MO - MO / i) % MO;

             invn[i] = (LL)invn[i - ] * inv[i] % MO;

         }

         int ans = ;

         for(int i = ; i <= k; i++) {

             ans += (LL)C(k, i) * qpow( * i - k, n) % MO;

             ans %= MO;

         }

         int temp = qpow((MO + ) / , k);

         printf("%lld\n", ((LL)temp * ans % MO + MO) % MO);

         return;

     }

 }

 int main() {

     scanf("%d%d%d", &n, &k, &d);

     if(d == ) {

         printf("%d\n", qpow(k, n));

         return ;

     }

     if(n <=  && k <= ) {

         DP::solve();

         return ;

     }

     if(d == ) {

         D2::solve();

         return ;

     }

     return ;

 }