#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("p2sah.in");
ofstream fout("p2sah.out");
long long int MOD=100003, y[4][4], Mat[4];

long long int DQ1(int n)
{if(n==0)return 1;
 else
 {long long int t=DQ1(n/2);
  if(n%2==1)return (((t*t)%MOD)*3)%MOD;
  else return (t*t)%MOD;
 }
}

void Inm(long long int x[4][4])
{long long int z[4][4];
 for(int i=1;i<=3;i++)
 for(int j=1;j<=3;j++)
 z[i][j]=0;

 for(int i=1;i<=3;i++)
 for(int j=1;j<=3;j++)
 for(int k=1;k<=3;k++)
 {z[i][j]+=(y[i][k]*x[k][j])%MOD;
  z[i][j]%=MOD;
 }
 for(int i=1;i<=3;i++)
 for(int j=1;j<=3;j++)
 y[i][j]=z[i][j]%MOD;
}

void DQ2(long long int x[4][4], int n)
{if(n==0)
 {for(int i=1;i<=3;i++)
  for(int j=1;j<=3;j++)
  y[i][j]=0;
  y[1][1]=y[2][2]=y[3][3]=1;
 }
 else
 {DQ2(x, n/2);
  Inm(y);
  if(n%2==1)Inm(x);
 }
}

int main()
{   int cer, n, k;
    long long int x[4][4];
    fin>>cer>>n>>k;
    if(cer==1)
    fout<<DQ1(k-1);
    else
    {if(n-k==0)fout<<1;
     else if(n-k==1)fout<<2;
     else
     {x[1][1]=x[1][3]=x[2][1]=x[2][2]=0;
      x[1][2]=x[3][1]=x[3][3]=x[3][2]=x[2][3]=1;
      DQ2(x, n-2-k);

      Mat[1]=1, Mat[2]=2, Mat[3]=4;

      Mat[3]=(Mat[1]*y[3][1])%MOD+(Mat[2]*y[3][2])%MOD+(Mat[3]*y[3][3])%MOD;

      fout<<Mat[3]%MOD;
     }
    }
    /*for(int i=1;i<=3;i++, cout<<endl)
      for(int j=1;j<=3;j++)cout<<y[i][j]<<" ";
    */
    return 0;
}