#include <fstream>

using namespace std;
int p,sol[2],m[2][2];
long long b[2],c[2][2];

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

void multiply1()
{
    int i,k;
    for(i=0;i<2;i++)
    {
        b[i]=0;
        for(k=0;k<2;k++)
            b[i]+=1LL*sol[k]*m[k][i];
    }
    for(i=0;i<2;i++)
        sol[i]=b[i]%666013;
}

void multiply2()
{
    int i,j,k;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
        {
            c[i][j]=0;
            for(k=0;k<2;k++)
                c[i][j]+=1LL*m[i][k]*m[k][j];
        }
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            m[i][j]=c[i][j]%666013;
}

int main()
{
    sol[1]=1;
    m[0][1]=m[1][0]=m[1][1]=1;
    in>>p; p--;
    while(p)
    {
        if(p%2==1)
            multiply1();
        multiply2();
        p=p/2;
    }
    out<<sol[1]<<'\n';
    return 0;
}