// napisane Monikou
// nasobenie matic v (2^M*K)^3*log N

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>

#define SIZE(s) ((int)((s).size()))
#define FOREACH(it,vec) for(typeof((vec).begin())it=(vec).begin();it!=(vec).end();++it)
#define REP(i,n) for(int i=0;i<(int)(n);++i)

#define MAXN 100
#define MAXM 8
#define MATICA 1000
#define MOD 420047

using namespace std;

int N,M,K;
long long A[MATICA][MATICA];
long long B[MATICA][MATICA];
long long tmp[MATICA][MATICA];
vector<long long> P;

void load_matrix() {
  memset(A,0,sizeof(A));
  REP(i,SIZE(P))
    REP(j,SIZE(P))
      if ((P[i] & P[j])==0) { 
        int cnt = 0;
        REP(l,M) if (P[j]&(1LL<<l)) ++cnt;
        REP(k,K+1) {
          if (cnt+k > K) break;
          A[i*(K+1)+k][j*(K+1)+k+cnt] = 1;
        }
      }
}

void print() {
  REP(i,SIZE(P)*(K+1)) {
    REP(j,SIZE(P)*(K+1))
      cout << A[i][j] << " ";
    cout << endl;
  }
  cout << endl;
}
    

void times(void) {
  memset(tmp,0,sizeof(tmp));
  REP(i,SIZE(P)*(K+1))
    REP(j,SIZE(P)*(K+1)) 
      REP(k,SIZE(P)*(K+1)) {
        tmp[i][j]+=A[i][k]*B[k][j];
        tmp[i][j]%=MOD;
      }
  REP(i,SIZE(P)*(K+1))
    REP(j,SIZE(P)*(K+1)) B[i][j] = tmp[i][j];
}

void times2(void) {
  memset(tmp,0,sizeof(tmp));
  REP(i,SIZE(P)*(K+1))
    REP(j,SIZE(P)*(K+1)) 
      REP(k,SIZE(P)*(K+1)) {
        tmp[i][j]+=B[i][k]*B[k][j];
        tmp[i][j]%=MOD;
      }
  REP(i,SIZE(P)*(K+1))
    REP(j,SIZE(P)*(K+1)) B[i][j] = tmp[i][j];
}

int main(void) {
  scanf("%d",&N); scanf("%d",&M); scanf("%d",&K);
  if (N==0) { printf("0\n"); return 0; }
  
  for(long long i=0;i<(1LL<<M);++i)
    if ((i & (i<<1))==0) P.push_back(i);

  load_matrix();

  vector<int> v;
  while(N > 0) {
    v.push_back(N%2);
    N/=2;
  }
  reverse(v.begin(),v.end());

  memset(B,0,sizeof(B));
  REP(i,MATICA) B[i][i] = 1;

  REP(i,SIZE(v)) {
    times2();
    if (v[i] == 1) times();
  }

  long long sum = 0;
  REP(i,SIZE(P)) {
    sum+=B[0][i*(K+1)+K];
    sum%=MOD;
  }
  printf("%lld\n",sum);
  return 0;
}