#include <iostream>
#include <fstream>

using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");

const int L =666013;

long long A[3][3];
long long C[3][3];
long long B[3][3];
long long D[3][3];

void inmultirematrici(long long A[3][3],long long B[3][3],long long C[3][3])
{

   C[1][1] = (((A[1][1] * B[1][1]) % L) + ((A[1][2] * B[2][1]) % L)) % L;
   C[1][2] = (((A[1][1] * B[1][2]) % L) + ((A[1][2] * B[2][2]) % L)) % L;
   C[2][1] = (((A[2][1] * B[1][1]) % L) + ((A[2][2] * B[2][1]) % L)) % L;
   C[2][2] = (((A[2][1] * B[1][2]) % L) + ((A[2][2] * B[2][2]) % L)) % L;

}

int lgputmatrici(long long C[3][3],int K)
{
   A[1][1] = 1;
    A[1][2] = 0;
    A[2][1] = 0;
    A[2][2] = 1;
   while(K > 0)
   {
       if(K & 1)
       {
        for(int i = 1;i <= 2;i++)
            for(int j = 1;j <= 2;j++)
              B[i][j] = A[i][j];
        inmultirematrici(B,C,A);
        K--;
        }
       for(int i = 1;i <= 2;i++)
            for(int j = 1;j <= 2;j++)
              B[i][j] = C[i][j];
         for(int i = 1;i <= 2;i++)
            for(int j = 1;j <= 2;j++)
              D[i][j] = C[i][j];
         inmultirematrici(B,D,C);
         K>>=1;
   }

   long long rez = 0;
   for(int i = 1;i <= 2;i++)
        for(int j = 1;j <= 2;j++)
        {
            rez+=A[i][j];
            rez %= L;
        }
        return rez;
}
int main()
{
    long long K;
    in >> K;
    K-=3;
    C[1][1] = 0;
    C[1][2] = 1;
    C[2][1] = 1;
    C[2][2] = 1;

    out << lgputmatrici(C,K) <<" ";
    return 0;
}