// Problem: P5548 [BJ United Round #3] 押韵
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5548
// Memory Limit: 500 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define endl '\n' 
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int P=1049874433;
void chkmax(int &x,int y){if(x<y)x=y;}
void chkmin(int &x,int y){if(x>y)x=y;}
int qpow(int a,int k,int p=P){
	int ret=1;
	while(k){
		if(k&1)ret=1ll*ret*a%p;
		a=1ll*a*a%p;
		k>>=1;
	}
	return ret;
}
int norm(int x){return x>=P?x-P:x;}
int reduce(int x){return x<0?x+P:x;}
void add(int&x,int y){if((x+=y)>=P)x-=P;}
union mi{
	int w;
	mi(){w=0;}
	mi(int u){u%=P,w=u+(u<0?P:0);}
	explicit operator int()const{return w;}
};
mi operator+(const mi&a,const mi&b){
	return mi(a.w+b.w-(a.w+b.w>=P?P:0));
}
mi operator-(const mi&a,const mi&b){
	return mi(a.w-b.w+(a.w<b.w?P:0));
}
mi operator*(const mi&a,const mi&b){
	return mi(1ll*a.w*b.w%P);
}
bool operator==(const mi&a,const mi&b){
	return a.w==b.w;
}
bool operator!=(const mi&a,const mi&b){
	return a.w!=b.w;
}
bool operator<(const mi&a,const mi&b){
	return a.w<b.w;
}
bool operator>(const mi&a,const mi&b){
	return a.w>b.w;
}
bool operator>=(const mi&a,const mi&b){
	return a.w>=b.w;
}
bool operator<=(const mi&a,const mi&b){
	return a.w<=b.w;
}
mi&operator+=(mi&a,const mi&b){
	a.w=a.w+b.w-(a.w+b.w>=P?P:0);
	return a;
}
mi&operator-=(mi&a,const mi&b){
	a.w=a.w-b.w+(a.w<b.w?P:0);
	return a;
}
mi&operator*=(mi&a,const mi&b){
	a.w=1ll*a.w*b.w%P;
	return a;
}
mi operator-(const mi&a){
	return mi(a.w?P-a.w:0);
}
mi&operator++(mi&a){
	a.w=a.w+1-(a.w+1>=P?P:0);
	return a;
}
mi&operator--(mi&a){
	a.w=a.w-1+(a.w?0:P);
	return a;
}
struct IO_Tp {
    const static int _I_Buffer_Size = 2 << 22;
    char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer, *_I_end= _I_Buffer + _I_Buffer_Size;

    const static int _O_Buffer_Size = 2 << 22;
    char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;

    IO_Tp() { fread(_I_Buffer, 1, _I_Buffer_Size, stdin); }
    ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }

    IO_Tp &operator>>(int &res) {
    	int f=1;
        while (_I_pos!=_I_end&&!isdigit(*_I_pos)&&(*_I_pos)!='-') ++_I_pos;
        assert(_I_pos!=_I_end);
        if(*_I_pos=='-')f=-1,++_I_pos;
        res = *_I_pos++ - '0';
        while (_I_pos!=_I_end&&isdigit(*_I_pos)) res = res * 10 + (*_I_pos++ - '0');
        res*=f;
        assert(_I_pos!=_I_end);
        return *this;
    }
    
    IO_Tp &operator>>(mi &res) {
    	int f=1;
        while (_I_pos!=_I_end&&!isdigit(*_I_pos)&&(*_I_pos)!='-') ++_I_pos;
        assert(_I_pos!=_I_end);
        if(*_I_pos=='-')f=-1,++_I_pos;
        res = *_I_pos++ - '0';
        while (_I_pos!=_I_end&&isdigit(*_I_pos)) res = res * 10 + (*_I_pos++ - '0');
        res*=f;
        assert(_I_pos!=_I_end);
        return *this;
    }
    
    IO_Tp &operator>>(string &res){
    	res="";
    	auto blank=[&](char ch){
    		if(ch==' '||ch=='\n'||ch=='\r'||ch=='	'||ch=='\0')return 1;
    		return 0;
		};
		while(_I_pos!=_I_end&&blank(*_I_pos)) ++_I_pos;
    	while (_I_pos!=_I_end&&!blank(*_I_pos))res += *_I_pos++;
    	assert(_I_pos!=_I_end);
    	return *this;
	} 

    IO_Tp &operator<<(int n) {
    	if(n<0)*_O_pos++='-',n=-n;
        static char _buf[10];
        char *_pos = _buf;
        do
            *_pos++ = '0' + n % 10;
        while (n /= 10);
        while (_pos != _buf) *_O_pos++ = *--_pos;
        return *this;
    }
    
    IO_Tp &operator<<(mi n) {
    	if(n<0)*_O_pos++='-',n=-n;
        static char _buf[10];
        char *_pos = _buf;
        do
            *_pos++ = '0' + n.w % 10;
        while (n.w /= 10);
        while (_pos != _buf) *_O_pos++ = *--_pos;
        return *this;
    }

    IO_Tp &operator<<(char ch) {
        *_O_pos++ = ch;
        return *this;
    }
    
    IO_Tp &operator<<(string &res){
    	for (char ch:res) *_O_pos++ = ch;
    	return *this;
	} 
} IO;
typedef vector<mi> vec;
struct Maths{
	int n;
	vec fac,invfac,inv;
	void build(int n){
		this->n=n;
		fac.resize(n+1);
		invfac.resize(n+1);
		inv.resize(n+1);
		fac[0]=1;
		rep(k,1,n)fac[k]=fac[k-1]*k;
		inv[1]=inv[0]=1;
		rep(k,2,n)inv[k]=-(P/k)*inv[P%k];
		invfac[0]=1;
		rep(k,1,n)invfac[k]=invfac[k-1]*inv[k];
	}
	Maths(){build(1);}
	void chk(int k){
		int lmt=n;
		if(k>lmt){while(k>lmt)lmt<<=1;build(lmt);}
	}
	mi cfac(int k){return chk(k),fac[k];}
	mi cifac(int k){return chk(k),invfac[k];}
	mi cinv(int k){return chk(k),inv[k];}
	mi binom(int n,int m){
		if(m<0||m>n)return 0;
		return cfac(n)*cifac(m)*cifac(n-m);
	}
}math;
const int K=2005*2;
int n,k,d;
mi f[K][K];
int main(){
	IO>>n>>k>>d;n=1ll*n*d%(P-1);
	if(n==0)n=P-1;
	if(d==1)IO<<qpow(k,n)<<endl,exit(0);
	#define binom math.binom
	else if(d==2){
		mi ans=0;
		rep(i,0,k)ans+=binom(k,i)*(mi)qpow(2*i-k,n);
		IO<<ans*mi(qpow((P+1)/2,k))<<endl;
	}else if(d==3){
		mi omega=72193119,ans=0;
		rep(i,0,k)rep(j,0,k-i)
			ans+=binom(k,i)*binom(k-i,j)*qpow(mi(i+j*omega+(k-i-j)*omega*omega).w,n);
		IO<<ans*mi(qpow(699916289,k))<<endl;
	}else if(d==4){
		mi omega=227660408,ans=0;
		rep(i,0,k)rep(j,0,k)
			ans+=binom(k,i)*binom(k,j)*qpow(mi((i-j)+omega*(i+j-k)).w,n);
		IO<<ans*mi(qpow(787405825,k))<<endl;
	}else{
		mi omega=72193120;
		math.chk(2*k);
		rep(i,0,k)f[i][k-i]=binom(k,i);
		rep(i,k+1,2*k)f[i][0]=f[0][i]=binom(k,i-k);
		rep(i,1,2*k)rep(j,max(k-i+1,1),2*k){
			f[i][j]=mi(k-i+1)*(f[i-1][j+1]+f[i-1][j-1]);
			if(i>1)f[i][j]+=mi(k*2+2-i)*(f[i-2][j+1]+f[i-2][j]);
			f[i][j]-=mi(i)*f[i][j-1];
			f[i][j]*=math.cinv(i);
		}
		mi ans=0;
		rep(i,0,2*k)rep(j,0,2*k)if(f[i][j].w)
			ans+=f[i][j]*qpow(mi(i-k+(j-k)*omega).w,n);
		IO<<ans*qpow(874895361,k)<<endl;
	}
	return 0;
}