#include <cstdio>

using namespace std;
FILE *in=fopen ("kfib.in","r");
FILE *out=fopen ("kfib.out","w");
const int mod=666013;
long long x[3][3],y[3][3],k;
void inmultire (long long a[3][3],long long b[3][3])
{
    long long aux[3][3];
    for (int i=1; i<=2; i++)
        for (int j=1; j<=2; j++)
        {
            aux[i][j]=0;
            for (int p=1; p<=2; p++)
                aux[i][j]=aux[i][j]%mod+(a[i][p]%mod)*(b[p][j]%mod);
        }
    for (int i=1; i<=2; i++)
        for (int j=1; j<=2; j++)
            a[i][j]=aux[i][j]%mod;
}

int main()
{
    fscanf (in,"%lld",&k);
    x[1][2]=x[2][2]=x[2][1]=1;
    y[1][1]=y[2][2]=1;
    k--;
    while (k!=0)
    {
        if (k%2!=0)
            inmultire (y,x);
        k/=2;
        inmultire(x,x);
    }
    fprintf (out,"%lld",y[2][2]);
    return 0;
}