#include <fstream>
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");

const long long mod = 666013;
long long Z[3][3],Sol[3][3],aux[3][3],n,i,j;

int main()
{
  cin>>n;
  --n;
  Z[1][1]=0; Z[1][2]=1; Z[2][1]=1; Z[2][2]=1;
  for (i=1;i<=2;++i) 
     for (j=1;j<=2;++j) Sol[i][j]=Z[i][j];
  while(n){
          if (n%2){ 
                     aux[1][1]=(Sol[1][1]*Z[1][1]+Sol[1][2]*Z[2][1])%mod;
                     aux[1][2]=(Sol[1][1]*Z[1][2]+Sol[1][2]*Z[2][2])%mod;
                     aux[2][1]=(Sol[2][1]*Z[1][1]+Sol[2][2]*Z[2][1])%mod;
                     aux[2][2]=(Sol[2][1]*Z[1][2]+Sol[2][2]*Z[2][2])%mod;  
                     for (i=1;i<=2;++i) 
                        for (j=1;j<=2;++j) Sol[i][j]=aux[i][j];
                     --n;
                    }
              else {
                    aux[1][1]=(Z[1][1]*Z[1][1]+Z[1][2]*Z[2][1])%mod;
                    aux[1][2]=(Z[1][1]*Z[1][2]+Z[1][2]*Z[2][2])%mod;
                    aux[2][1]=(Z[2][1]*Z[1][1]+Z[2][2]*Z[2][1])%mod;
                    aux[2][2]=(Z[2][1]*Z[1][2]+Z[2][2]*Z[2][2])%mod;
                    for (i=1;i<=2;++i)
                       for (j=1;j<=2;++j) Z[i][j]=aux[i][j];
                    n/=2;
                    }
           }
  cout<<Sol[2][1];   
return 0;
}