#include<fstream>

using namespace std;

ifstream f("flip.in");
ofstream g("flip.out");

int putere(int a,int n,int q)
{int i;
int p=1;
if(a == 0)
	return 0;
	for( i = 1; i <= n; i++)
	{ 
		if(p > q)
		{
			p = p % q;
		}
		p=p*a;
	}
	
	return p%q;
}
int scadere(int a, int b,int q)
{
	if(a<b)
		return (a+q-b);
	else
		return (a-b);
}
int main()
{long n,m,k;
int  q = 40009,x,y,z,rez,n1,m1,k1;
	
	f>>n>>m>>k;
	n1 = n%q;
	if(n1==0)
		n1 = q;
	m1 = m%q;
	if(m1 == 0)
		m1 = q;
	k1 = k%q;
	
	n1=40009;
	m1=40009;
	x = putere(2,n1,q);
	y = putere(2,scadere(n1,k1+1,q)%q,q);
	z = ((scadere(n1,k1+1,q)%q)*putere(2,scadere(n1,k1+2,q)%q,q))%q;
	
	rez = scadere(x,y,q);
	rez = scadere(rez,z,q);
	
	rez = putere(rez,m1,q);
	g<<rez;
return 0;
}