#include <fstream>

using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
bool f[1][2];
long long r[1][2];
long long masca[2][2];
long long putere[2][2];
const int MOD=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]+(a[i][d]*b[d][j])%MOD)%MOD;
    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()
{
   f[0][0]=1;
   f[0][1]=1;
long long n;
cin>>n;
masca[0][0]=0;
masca[0][1]=1;
masca[1][0]=1;
masca[1][1]=1;
exponentiere(n);
for(int i=0;i<1;i++)
    for(int j=0;j<2;j++)
         for(int d=0;d<1;d++)
           r[i][j]=(r[i][j]+(f[i][d]*putere[d][j])%MOD)%MOD;
        cout<<r[0][1];
    return 0;
}