#include <stdio.h>
using namespace std;

#define MOD 666013

long long F[2][3], Z[3][3], copie_z[3][3];
int bin[1001];
int n, i, j, k, p;
long long K;

void inmultire_Z (long long a[3][3], long long b[3][3])
{
    long long c[3][3];
    for (i=0; i<=2; ++i)
        for (j=0; j<=2; ++j)
            c[i][j] = 0;

    for (i=1; i<=2; ++i)
        for (j=1; j<=2; ++j)
            for (k=1; k<=2; ++k)
                c[i][k] += (a[i][j] * b[j][k]) % MOD;

    for (i=1; i<=2; ++i)
        for (j=1; j<=2; ++j)
            a[i][j] = c[i][j];
}

void inmultire_F (long long a[2][3], long long b[3][3])
{
    long long c[2][3];
    c[1][1] = c[1][2] = 0;

    for (i=1; i<=1; ++i)
        for (j=1; j<=2; ++j)
            for (k=1; k<=2; ++k)
                c[i][k] += (a[i][j] * b[j][k]) % MOD;

    a[1][1] = c[1][1];
    a[1][2] = c[1][2];
}

int main ()
{
    FILE *f = fopen ("kfib.in","r");
    FILE *g = fopen ("kfib.out","w");
    fscanf (f,"%lld", &K);

    F[1][1] = 0;
    F[1][2] = 1;

    copie_z[1][1] = 0;
    copie_z[1][2] = copie_z[2][1] = copie_z[2][2] = 1;

    Z[1][1] = 1;
    Z[2][2] = 1;

    K --;
    while (K)
    {
        n ++;
        bin[n] = K % 2;
        K /= 2;
    }

    for (p=n; p>=1; --p)
    {
        inmultire_Z (Z, Z);

        if (bin[p])
            inmultire_Z (Z, copie_z);
    }

   /* for (i=1; i<=2; ++i)
    {
        for (j=1; j<=2; ++j)
            printf ("%d ", Z[i][j]);
        printf ("\n");
    }*/

    inmultire_F (F, Z);

    //printf ("%lld %lld", F[1][1], F[1][2]);

    fprintf (g,"%lld\n", F[1][2]);

    fclose (g);
    fclose (f);
    return 0;
}