#include <iostream>
#include <fstream>

using namespace std;

long long n,i;
long long m[1001],sol[1001];
int inmult (long long v[])
{
    long long t1,t2,t3,t4,t11,t22,t33,t44;
    t1=sol[1];t11=v[1];
    t2=sol[2];t22=v[2];
    t3=sol[3];t33=v[3];
    t4=sol[4];t44=v[4];
    sol[1]=(1LL*t11*t1+1LL*t22*t3)%666013;
    sol[2]=(1LL*t11*t2+1LL*t22*t4)%666013;
    sol[3]=(1LL*t33*t1+1LL*t44*t3)%666013;
    sol[4]=(1LL*t33*t2+1LL*t44*t4)%666013;
}
int main()
{
    ifstream fin ("kfib.in");
    ofstream fout ("kfib.out");
    fin>>n;
    m[1]=0;m[2]=1;m[3]=1;m[4]=1;
    sol[1]=1;sol[2]=0;sol[3]=0;sol[4]=1;
    n--;
    for(i=0;(1<<i)<=n;++i)
    {
        if(((1<<i)& n)>0)
        {
            inmult(m);
        }
    long long t1,t2,t3,t4;
    t1=m[1];t2=m[2];t3=m[3];t4=m[4];
    m[1]=(1LL*t1*t1+1LL*t2*t3)%666013;
    m[2]=(1LL*t1*t2+1LL*t2*t4)%666013;
    m[3]=(1LL*t3*t1+1LL*t4*t3)%666013;
    m[4]=(1LL*t3*t2+1LL*t4*t4)%666013;
    }
    if(n<3)
    {
     if(n<2)fout<<1;
     else fout<<2;
    }
    else
    fout<<(sol[1]+sol[2])%666013;
    return 0;
}