#include <fstream>
#include <string.h>

#define MOD 666013

using namespace std;

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

int n, colMatrix[3][3], fullMatrix[3][3];

void initMatrix(int A[][3], int B[][3])
{
    A[1][1]=0;
    A[1][2]=A[2][1]=A[2][2]=1;
    B[1][1]=0;
    B[2][1]=1;
}

void inmultMatrix(int A[][3], int B[][3])
{
    int C[3][3];
    memset(C, 0, sizeof(C));

    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
            for(int k=1; k<=2; k++)
            {
                C[i][j]+=(1ll*A[i][k]*B[k][j])%MOD;
                C[i][j]%=MOD;
            }
    memcpy(B, C, sizeof(C));
}

int main()
{
    initMatrix(fullMatrix, colMatrix);
    fin>>n;
    if(n==0)
    {
        fout<<0;
        return 0;
    }
    if(n==1)
    {
        fout<<1;
        return 0;
    }
    n--;
    while(n)
    {
        if(n&1)
        {
            n--;
            inmultMatrix(fullMatrix, colMatrix);
        }
        n/=2;
        inmultMatrix(fullMatrix, fullMatrix);
    }
    fout<<colMatrix[2][1];
}