#include<fstream>
using namespace std;
ifstream f("kfib.in");
    ofstream g("kfib.out");
long v[4];
void prodmatrice(long o[4],long u[4],long s[4])
{
    s[0]=(o[0]*u[0]+o[1]*u[2])%666013;
    s[1]=(o[0]*u[2]+o[1]*u[3])%666013;
    s[2]=(o[2]*u[0]+o[3]*u[2])%666013;
    s[3]=(o[2]*u[1]+o[3]*u[3])%666013;
}
void putere(long x, long s[4])
{
    long c[4],i,aux[4],j;
    for(i=0;i<=3;i++)
        c[i]=v[i];
    s[0]=1;s[1]=0;s[2]=0;s[3]=1;
    for(j=0;(1<<j)<=x;j++)
    {
        if((1<<j)&x)
        {
            prodmatrice(s,c,aux);
            for(i=0;i<=3;i++)
               s[i]=aux[i];
        }
        prodmatrice(c,c,aux);
        for(i=0;i<=3;i++)
           c[i]=aux[i];

    }
}
int main()
{
    long n,i,s[4];
    f>>n;
    v[0]=0;v[1]=1;v[2]=1;v[3]=1;
    putere(n-1,s);
    g<<s[3];
}