#include <iostream>
using namespace std;
#include <fstream>
long long a[2][2],n;
ofstream g("kfib.out");

unsigned pow (long long a[2][2],long long n)
{
    unsigned i,j,k;
     if (n==1)
        return 0;
    long long c[2][2]={0},u[2][2]={0};
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
                for(k=0;k<2;k++)
                    c[i][j]=(c[i][j]+a[i][k]*a[k][j])%666013;
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
                {u[i][j]=a[i][j];
                a[i][j]=c[i][j];}



    if(n%2==0)
        pow(a,n/2);
    if(n%2==1)
    {   pow(a,n/2);
    long long d[2][2]={0};
         for(i=0;i<2;i++)
            for(j=0;j<2;j++)
                for(k=0;k<2;k++)
                    d[i][j]=(d[i][j]+u[i][k]*a[k][j])%666013;
        for(i=0;i<2;i++)
        for(j=0;j<2;j++)
        a[i][j]=d[i][j];}
}

void simplu (long long a[2][2], long long s[2][1])
{
    unsigned i,k;
    long long x[2][1]={0};
    for(i=0;i<2;i++)
        for(k=0;k<2;k++)
            x[i][0]=(x[i][0]+s[k][0]*a[i][k])%666013;
    g<<x[0][0];

}


int main ()
{
    long long s[2][1];
    s[0][0]=1,s[1][0]=0,a[0][0]=1,a[0][1]=1,a[1][0]=1,a[1][1]=0;
    ifstream f("kfib.in");

    f>>n;
    if (n==1)
        {
        g<<1;
        return 0;
        }
    if(n==0)
    {
        g<<0;
        return 0;
    }
        n--;
     pow(a,n);
    simplu(a,s);
return 0;}