#include <iostream>
#include<fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int main()
{
    unsigned long long int n,r=666013,i,a,b,c,d,a1,a2,b1,b2,c1,c2,d1,d2,x,p;
        a1=0;
        b1=c1=d1=1;
        a=1;
        b=0;
        c=0;
        d=1;
        f>>x;
        if(x==1)
            g<<1<<'\n';
        else if(x==2)
            g<<2%r<<'\n';
        else
        {
            p=x-2;
            while(p!=0)
            {
                if(p&1==1)
                {
                    a2=a;
                    b2=b;
                    c2=c;
                    d2=d;
                    a=(a2*a1+b2*c1)%r;
                    b=(a2*b1+b2*d1)%r;
                    c=(c2*a1+d2*c1)%r;
                    d=(c2*b1+d2*d1)%r;
                }
                a2=a1;
                b2=b1;
                c2=c1;
                d2=d1;
                a1=(a2*a2+b2*c2)%r;
                b1=(a2*b2+b2*d2)%r;
                c1=(c2*a2+d2*c2)%r;
                d1=(c2*b2+d2*d2)%r;
                p>>=1;
            }
            g<<(b+d)%r<<'\n';
        }

    f.close();
    g.close();
    return 0;
}