#include <fstream>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int mod, k, a[2][2];

void Calc(int a[2][2], int p)
{
    if(p>1)
    {
        int b[2][2], t1, t2, t3, t4;
        t1=a[0][0];
        t2=a[0][1];
        t3=a[1][0];
        t4=a[1][1];
        b[0][0]=((t1*t1)%mod+(t2*t3)%mod)%mod;
        b[0][1]=((t1+t4)%mod*t2)%mod;
        b[1][0]=((t1+t4)%mod*t3)%mod;
        b[1][1]=((t4*t4)%mod+(t2*t3)%mod)%mod;
        Calc(b, p/2);
        if(p%2==0)
        {
            a[0][0]=b[0][0];
            a[0][1]=b[0][1];
            a[1][0]=b[1][0];
            a[1][1]=b[1][1];
        }
        if(p%2==1)
        {
            t1=((a[0][0]*b[0][0])%mod+(a[0][1]*b[1][0])%mod)%mod;
            t2=((a[0][0]*b[0][1])%mod+(a[0][1]*b[1][1])%mod)%mod;
            t3=((a[1][0]*b[0][0])%mod+(a[1][1]*b[1][0])%mod)%mod;
            t4=((a[1][0]*b[0][1])%mod+(a[1][1]*b[1][1])%mod)%mod;

            a[0][0]=t1;
            a[0][1]=t2;
            a[1][0]=t3;
            a[1][1]=t4;
        }
    }
}

int main()
{
    mod=666013;
    fin>>k;
    if(k==0)
        fout<<"0";
    if(k==1)
        fout<<"1";
    if(k>1)
    {
        a[0][0]=0;
        a[0][1]=a[1][0]=a[1][1]=1;
        Calc(a, k-1);
        fout<<a[1][1]%mod;
    }
    fin.close();
    fout.close();
    return 0;
}