#include <fstream>
using namespace std;

long inm[3][3];
void inmulteste_matrici(long prima[3][3],long doua[3][3])
{
    int i,j,k;
    for(i=0;i<3;++i)
        for (j=0;j<3;++j)
            inm[i][j]=0;

    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
            for(k=0;k<3;++k)
                inm[i][j]=(doua[i][k] * prima[k][j] + inm[i][j]) % 666013;

    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
            prima[i][j]=inm[i][j];
}



int main()
{
    ifstream f("kfib.in");
    int n;
    long mat1[3][3],mat2[3][3];
    f >> n;
    f.close();

    mat1[0][0]=mat1[0][1]=mat1[0][2]=mat1[1][0]=mat1[1][1]=mat1[2][0]=0;
    mat1[1][2]=mat1[2][1]=mat1[2][2]=1;

    mat2[0][0]=mat2[0][1]=mat2[0][2]=mat2[1][0]=mat2[1][2]=mat2[2][0]=mat2[2][1]=0;
    mat2[1][1]=mat2[2][2]=1;

    --n;

    while(n != 0)
    {
        if (n % 2 == 1)
            inmulteste_matrici(mat2,mat1);
        inmulteste_matrici(mat1,mat1);
        n=n>>1;
    }

    ofstream g("kfib.out");
    g << mat2[2][2];
    g.close();

    return 0;
    }