#include <fstream>

using namespace std;

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

const int MOD=666013;

int A[2][2]={{0, 1},
             {1, 1}};
int CA[2][2]={{0, 1},
              {1, 1}};

void ProdMat(int A[2][2], int B[2][2], int R[2][2]);
void PutMat(int A[2][2], int n);

int main()
{
    int p;
    in >> p;
    PutMat(A, p-1);
    out << A[1][1];
    return 0;
}

void ProdMat(int A[2][2], int B[2][2], int R[2][2])
{
    int aux[2][2];
    aux[0][0]=((long long)A[0][0]*B[0][0]%MOD+(long long)A[0][1]*B[1][0]%MOD);
    aux[0][1]=((long long)A[0][0]*B[0][1]%MOD+(long long)A[0][1]*B[1][1]%MOD);
    aux[1][0]=((long long)A[1][0]*B[0][0]%MOD+(long long)A[1][1]*B[1][0]%MOD);
    aux[1][1]=((long long)A[1][0]*B[0][1]%MOD+(long long)A[1][1]*B[1][1]%MOD);
    R[0][0]=aux[0][0];
    R[0][1]=aux[0][1];
    R[1][0]=aux[1][0];
    R[1][1]=aux[1][1];
}

void PutMat(int A[2][2], int n)
{

    if(n==1) return;
    if(n%2==1)
    {
        PutMat(A, n/2);
        ProdMat(A, A, A);
        ProdMat(CA, A, A);
    }
    else
    {
        PutMat(A, n/2);
        ProdMat(A, A, A);
    }
}