#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long k;

void prodmat(long long a1, long long b1, long long c1, long long d1, long long a2, long long b2, long long c2, long long d2, long long &r1, long long &r2, long long &r3, long long &r4)
{
    r1=( (a1*a2)%666013 + (b1*c2)%666013 ) %666013;
    r2=( (a1*b2)%666013 + (b1*d2)%666013 ) %666013;
    r3=( (c1*a2)%666013 + (d1*c2)%666013 ) %666013;
    r4=( (c1*b2)%666013 + (d1*d2)%666013 ) %666013;
}

void fastexp(long long &a, long long &b, long long &c, long long &d, long long n)
{
    long long aa=a,bb=b,cc=c,dd=d;
    if(n==0)
    {
        a=d=1;
        b=c=0;
        return;
    }
    if(n%2)
    {
        fastexp(aa,bb,cc,dd,n-1);
        prodmat(0,1,1,1,aa,bb,cc,dd,a,b,c,d);
        return;
    }
    fastexp(aa,bb,cc,dd,n/2);
    prodmat(aa,bb,cc,dd,aa,bb,cc,dd,a,b,c,d);
    return;
}

int main()
{
    f>>k;
    long long a,b,c,d;
    a=0;
    b=c=d=1;
    fastexp(a,b,c,d,k-1);
    //g<<a<<' '<<b<<'\n'<<c<<' '<<d<<"\n\n";
    g<<d%666013<<'\n';
    f.close(); g.close();
    return 0;
}