#include <cstdio>
#include <cstring>
#include <fstream>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long k,p11,p12,p22,sol[3][3],a[3][3];
void p2()
{
    p11=(a[1][1]*a[1][1]+a[1][2]*a[2][1])%mod;
    p12=(a[1][1]*a[1][2]+a[1][2]*a[2][2])%mod;
    p22=(a[2][1]*a[1][2]+a[2][2]*a[2][2])%mod;
    a[1][1]=p11;
    a[1][2]=a[2][1]=p12;
    a[2][2]=p22;
}
void p1()
{
    p11=(sol[1][1]*a[1][1]+sol[1][2]*a[2][1])%mod;
    p12=(sol[1][1]*a[1][2]+sol[1][2]*a[2][2])%mod;
    sol[1][1]=p11;
    sol[1][2]=p12;
}

int main()
{
    a[1][1]=0;a[1][2]=1;
    a[2][2]=1;a[2][1]=1;
    sol[1][1]=0;
    sol[1][2]=1;
    f>>k;k--;
    if(k==-1)g<<"0";
    else
    {
        for(;k;k>>=1)
        {
            if(k&1)p1();
            p2();
        }
        g<<sol[1][2]%mod;
    }
    return 0;
}