#include <fstream>
using namespace std;
ifstream f("2sah.in");
ofstream g("2sah.out");
unsigned long long n,k,p,a[10001][10001];
void constr(){
    unsigned long long i=2,j;
    a[1][n+1]=1;
    for(j=2;j<=n+1;j++)
        for(i=1;i<=2*n+1;i++)
            a[j][i]=a[j-1][i-1]+a[j-1][i]+a[j-1][i+1];
}
unsigned long long putere(unsigned long long n, unsigned long long k)
{
    unsigned long long m;
    if(k==1) return n;
    else if(k%2)
    {
        m=putere(n,k/2);
        return ((m*m)%100003*n)%100003;
    }
    else
    {
        m=putere(n,k/2);
        return (m*m)%100003;
    }
}
int main()
{
    unsigned long long x,i,j,s=0;
    f>>p>>n>>k;
    if(p==1){
        g<<putere(3,k-1)%100003;}
    if(p==2){
        constr();
        i=1;
        j=k;
        while(i<n+1 && j<2*n+1){
            s+=a[i][j]%100003;
            i++;
            j+=2;}
        g<<s;
    }
    /*for(j=1;j<=n+1;j++){
        for(i=1;i<=2*n+1;i++)
            g<<a[j][i]<<" ";
        g<<'\n';}*/
    return 0;
}