#include <iostream>
#include<fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long z[3][3],v[3][3],w[3][3],p,nr,x1,x2,x3,x4,y1,y2,y3,y4;
int mod(long long x)
{
    x%=666013;
    return x;
}
int main()
{
    f>>nr;
    nr=mod(nr);
    z[1][1]=0;z[1][2]=1;z[2][1]=1;z[2][2]=1;
    w[1][1]=0;v[1][1]=0;
    w[1][2]=1;v[1][2]=1;
    w[2][1]=1;v[2][1]=1;
    w[2][2]=1;v[2][2]=1;
    p=nr-3;
    while(p>0)
    {
        if(p&1)
        {
            x1=mod(v[1][1]);x2=mod(v[1][2]);x3=mod(v[2][1]);x4=mod(v[2][2]);
            y1=mod(x1*z[1][1]+x2*z[2][1]);
            y2=mod(x1*z[1][2]+x2*z[2][2]);
            y3=mod(x3*z[1][1]+x4*z[2][1]);
            y4=mod(x3*z[1][2]+x4*z[2][2]);
            v[1][1]=(y1);v[1][2]=(y2);v[2][1]=(y3);v[2][2]=(y4);

            p--;
        }

        else
        {
            x1=mod(z[1][1]);x2=mod(z[1][2]);x3=mod(z[2][1]);x4=mod(z[2][2]);
            y1=mod(x1*x1+x2*x3);
            y2=mod(x1*x2+x2*x4);
            y3=mod(x3*x1+x4*x3);
            y4=mod(x3*x2+x4*x4);
            z[1][1]=(y1);z[1][2]=(y2);z[2][1]=(y3);z[2][2]=(y4);
            p>>=1;
        }


    }

    y2=mod(v[1][2]+v[2][2]);
    g<<(y2);

}