#include<fstream>
using namespace std;
    struct patru
    {
        long long a,b,c,d;
    };
    patru x,y,z,p;
patru f(patru x,patru y)
    {
        patru t;
        t.a=x.a*y.a+x.b*y.c;
        t.b=x.a*y.b+x.b*y.d;
        t.c=x.c*y.a+x.d*y.c;
        t.d=x.c*y.b+x.d*y.d;
        t.a=t.a%666013;
        t.b=t.b%666013;
        t.c=t.c%666013;
        t.d=t.d%666013;
        return t;
    }
int k;
fstream fin,fout;
int main()
{
    fin.open("kfib.in",ios::in);
    fout.open("kfib.out",ios::out);
    fin>>k;
    p.a=1;
    p.b=0;
    p.c=0;
    p.d=1;
    z.a=0;
    z.b=1;
    z.c=1;
    z.d=1;
    while(k>0)
    {
        if(k%2==1)
        {
            p=f(p,z);
        }
        z=f(z,z);
        k=k/2;
    }
    fout<<p.b;
    fout.close();
    fin.close();
    return 0;
}