#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=,MOD=;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,k,p;

struct Matrix{

    int a[N][N];

    int* operator [](int x){return a[x];}

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

}g;

int st[N],m;

inline void mod(int &x){if(x>=MOD) x-=MOD;}

Matrix operator *(Matrix a,Matrix b){

    Matrix re;int n=m;

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

        for(int i=;i<n;i++) if(a[i][k])

            for(int j=;j<n;j++) if(b[k][j])

                mod(re[i][j]+=a[i][k]*b[k][j]%MOD);

    return re;

}

Matrix operator ^(Matrix a,int b){

    Matrix re;int n=m;

    for(int i=;i<n;i++) re[i][i]=;

    for(;b;b>>=,a=a*a)

        if(b&) re=re*a;

    return re;

}

void dfs(int d,int num,int s){//printf("Dfs %d %d %d\n",d,num,s);

    if(num==) {st[m++]=s;return;}

    for(int i=d;i<p-;i++) dfs(i+,num-,s|(<<i));

}

void build(){

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

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

            int s= st[i]^(st[j]>>);//printf("build %d %d %d\n",st[i],st[j],s);

            if(s == (s&-s)) g[i][j]=;

        }

}

int main(){

    freopen("in","r",stdin);

    n=read();k=read();p=read();

    dfs(,k-,);

    //for(int i=0;i<m;i++) printf("st %d  %d\n",i,st[i]);

    build();

    //for(int i=0;i<m;i++) for(int j=0;j<m;j++) printf("%d%c",g[i][j],j==m-1?'\n':' ');puts("");

    Matrix a,t=g^(n-k);

    //for(int i=0;i<m;i++) for(int j=0;j<m;j++) printf("%d%c",t[i][j],j==m-1?'\n':' ');;puts("");

    a[][]=;

    a=a*t;

    //for(int i=0;i<m;i++) for(int j=0;j<m;j++) printf("%d%c",a[i][j],j==m-1?'\n':' ');puts("");

    printf("%d",a[][]);

}