#include <fstream>
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
long long r[1][2];
long long masca[2][2];
long long putere[2][2];
const int M=666013;
void inmultire(long long a[][2],long long b[][2])
{
    long long c[2][2]={0};
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int d=0;d<2;d++)
                  c[i][j]=(c[i][j]%M+a[i][d]*b[d][j]*1LL%M)%M;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
           a[i][j]=c[i][j];
}
void exponentiere(long long n)
{
    if(n==0)
      {
            putere[0][0]=1;
            putere[0][1]=0;
            putere[1][0]=0;
            putere[1][1]=1;
            return;
      }
      exponentiere(n/2);
      inmultire(putere,putere);
      if(n%2==1)
         inmultire(putere,masca);
}
int main()
{
long long n;
cin>>n;
masca[0][0]=0;
masca[0][1]=1;
masca[1][0]=1;
masca[1][1]=1;
exponentiere(n);
cout<<putere[0][1];
    return 0;
}