#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    int k;
    long long a,b,c,aa,bb,cc,arez,brez,crez,aarez,bbrez,ccrez;
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    fin>>k;
    a=0;b=1;c=1;
    arez=0;brez=1;crez=1;
    const int x=666013;
    while(k)
    {
        if(k%2)
        {
            aarez=((arez*a)%x+(brez*b)%x)%x;
            bbrez=((arez*b)%x+(brez*c)%x)%x;
            ccrez=((brez*b)%x+(crez*c)%x)%x;
            arez=aarez;brez=bbrez;crez=ccrez;
        }
        k/=2;
        aa=((a*a)%x+(b*b)%x)%x;
        bb=((a*b)%x+(b*c)%x)%x;
        cc=((b*b)%x+(c*c)%x)%x;
        a=aa;b=bb;c=cc;
    }
    fout<<arez;
    return 0;
}