#include<bits/stdc++.h>
#define mod 30031
using namespace std;
int n,k,p,s,z[1100];
int hs(int x){return x&-x;}
int sum(int x){int r=0;for(int i=x;i>=1;i-=hs(i),r++);return r;}
struct node{
    int a[300][300];
    node operator * (const node &x)const{
        node y;
		memset(y.a,0,sizeof(y.a));
        for(int i=1;i<=s;i++)
            for(int j=1;j<=s;j++)
                for(int k=1;k<=s;k++)
                    y.a[i][j]+=a[i][k]*x.a[k][j]%mod,y.a[i][j]%=mod;
        return y;
    }
}ans,f;
int main(){
	freopen("busb.in","r",stdin);
	freopen("busb.out","w",stdout);
    scanf("%d%d%d",&n,&k,&p);n-=k;
    for(int i=0;i<(1<<p);i++)
        if(sum(i)==k&&(i&1))
		    z[++s]=i;
    for(int i=1;i<=s;i++)
        for(int j=1;j<=s;j++)
            if(sum((z[i]>>1)&z[j])==k-1)f.a[i][j]=1;
    for(int i=1;i<=s;i++)ans.a[i][i]=1;
    while(n){if(n&1)ans=ans*f;f=f*f;n>>=1;}
    printf("%d\n",ans.a[1][1]);
    return 0;
}