#include <iostream>
#include <fstream>
#define c 666013;
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
int k;
long long z[2][2],m[2][2],a[2][2];

void inmultire(long long zz[2][2], long long aa[2][2])
{ int i, j,k, aux[3][3];
for(i=0;i<2;i++)
    for(j=0;j<2;j++)
        aux[i][j]=0;
for(i=0;i<2;i++)
    for(j=0;j<2;j++)
        for(k=0;k<2;k++)
            aux[i][j]=(aux[i][j]+zz[i][k]*aa[k][j])%c;
 for(i=0;i<2;i++)
    for(j=0;j<2;j++)
        zz[i][j]=aux[i][j];
}


int main()
{ z[0][0]=a[0][0]=0;
  z[0][1]=a[0][1]=1;
  z[1][0]=a[1][0]=1;
  z[1][1]=a[1][1]=1;
  m[0][0]=0;
  m[0][1]=1;
  in>>k;
  k--;
  while(k)
    { if(k & 1)
        inmultire(z,a);
    inmultire(a,a);
     k>>=1;
    }
  z[0][0]%=c;
  z[0][1]%=c;
  out<<z[0][1];

  in.close();
  out.close();

    return 0;
}