#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

long long a[3][3],b[3][3],c[3][3],rez[3][3];
int n,p;

void prod_mat()
{
    a[1][1]=b[1][1]*c[1][1]+b[1][2]*c[2][1];
    a[1][2]=b[1][1]*c[1][2]+b[1][2]*c[2][2];
    a[2][1]=a[1][2];
    a[2][2]=a[1][1]+a[1][2];
}

int main()
{
    f >> n;
    if (n<3) g << 1; else
    {
        rez[1][1]=0; rez[1][2]=1; rez[2][1]=1; rez[2][2]=1;
        n-=3;
        while (n>0)
        {
            a[1][1]=0; a[1][2]=1; a[2][1]=1; a[2][2]=1;
            p=1;
            while (p*2<=n)
            {
                p*=2;
                b[1][1]=a[1][1]; b[1][2]=a[1][2]; b[2][1]=a[2][1]; b[2][2]=a[2][2];
                c[1][1]=a[1][1]; c[1][2]=a[1][2]; c[2][1]=a[2][1]; c[2][2]=a[2][2];
                prod_mat();
            }
            b[1][1]=rez[1][1]; b[1][2]=rez[1][2]; b[2][1]=rez[2][1]; b[2][2]=rez[2][2];
            c[1][1]=a[1][1]; c[1][2]=a[1][2]; c[2][1]=a[2][1]; c[2][2]=a[2][2];
            prod_mat();
            rez[1][1]=a[1][1]; rez[1][2]=a[1][2]; rez[2][1]=a[2][1]; rez[2][2]=a[2][2];
            n-=p;
        }
        //g << rez[1][1] << " " << rez[1][2] << " " << endl << rez[2][1] << " " << rez[2][2];
        g << (rez[2][1]+rez[2][2])%666013;
    }
    g.close();
    return 0;
}