#include <iostream>
#include<fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int z[3][3],v[3][3],w[3][3],p,nr,x1,x2,x3,x4,y1,y2,y3,y4;
int main()
{
    f>>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=v[1][1];x2=v[1][2];x3=v[2][1];x4=v[2][2];
            y1=x1*z[1][1]+x2*z[2][1];
            y2=x1*z[1][2]+x2*z[2][2];
            y3=x3*z[1][1]+x4*z[2][1];
            y4=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=z[1][1];x2=z[1][2];x3=z[2][1];x4=z[2][2];
            y1=x1*x1+x2*x3;
            y2=x1*x2+x2*x4;
            y3=x3*x1+x4*x3;
            y4=x3*x2+x4*x4;
            z[1][1]=y1;z[1][2]=y2;z[2][1]=y3;z[2][2]=y4;
            p>>=1;
        }


    }


    y1=w[1][1]+w[2][1];
    y2=v[1][2]+v[2][2];
    cout<<y2%666013;

}