#include <bits/stdc++.h>

 typedef long long ll;

 const int maxn=;

 const ll MOD=;

 using namespace std;

 ll tot; int sta[maxn];

 struct Matrix{

     ll m[maxn][maxn];

     Matrix(){memset(m,,sizeof(m));}

 };

 Matrix operator * (const Matrix& a,const Matrix& b){

     Matrix ans;

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

         for(int j=;j<=tot;j++)

             for(int k=;k<=tot;k++)

                 ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;

     return ans;

 }

 Matrix a,ans,f,tmp;

 int main(){

     ll n,m;int k;

     cin>>n>>m>>k;

     tot=(<<m)-;

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

         int num=,x=i;

         while(x){ if(x&)num++; x>>=; }

         if(num<=k){

             sta[i]=true;

             a.m[i>>][i]=;

             a.m[(i>>)+(<<(m-))][i]=;

         }

     }

     for(int i=;i<maxn;i++) tmp.m[i][i]=;

     while(n){

         if(n&) tmp=tmp*a;

         a=a*a;

         n>>=;

     }

     // for(int i=0;i<=tot;i++,puts(""))

     //     for(int j=0;j<=tot;j++)

     //         printf("%5d ",tmp.m[i][j]);

     ll cnt=;

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

         if(sta[i]){

             cnt=(cnt+tmp.m[i][i])%MOD;

         }

     }

     cout<<cnt<<endl;

     return ;

 }