#include <stdio.h>
#define MOD 666013
#define ORD 3

FILE *f, *g;
typedef unsigned long long ul;

/*      0 1
    z = 1 1
*/
ul b[ORD][ORD];
ul copieB[ORD][ORD];

/*
    rez = (F1 F2)
*/

ul rez[ORD-1][ORD];
ul copieRez[ORD-1][ORD];
int k;

void init();


int main()
{
    f = fopen("kfib.in", "r");
    g = fopen("kfib.out", "w");

    init();

    fscanf(f, "%d", &k);
    k--;

    while (k != 0){
        if (k%2 == 0){
            b[1][1] = (copieB[1][1]*copieB[1][1] + copieB[1][2]*copieB[2][1])%MOD;
            b[1][2] = (copieB[1][1]*copieB[1][2] + copieB[1][2]*copieB[2][2])%MOD;
            b[2][1] = (copieB[2][1]*copieB[1][1] + copieB[2][2]*copieB[2][1])%MOD;
            b[2][2] = (copieB[2][1]*copieB[1][2] + copieB[2][2]*copieB[2][2])%MOD;

            copieB[1][1] = b[1][1];
            copieB[1][2] = b[1][2];
            copieB[2][1] = b[2][1];
            copieB[2][2] = b[2][2];

            k /= 2;
        }else{
            rez[1][1] = (copieRez[1][1]*b[1][1] + copieRez[1][2]*b[2][1])%MOD;
            rez[1][2] = (copieRez[1][1]*b[1][2] + copieRez[1][2]*b[2][2])%MOD;

            copieRez[1][1] = rez[1][1];
            copieRez[1][2] = rez[1][2];

            k--;
        }
    }

    fprintf(g, "%d\n", rez[1][1]);

    fclose(f);
    fclose(g);

    return 0;
}

void init(){
    rez[1][1] = rez[1][2] = 1;
    copieRez[1][1] = copieRez[1][2] = 1;

    b[1][2] = b[2][1] = b[2][2] = 1;
    copieB[1][2] = copieB[2][1] = copieB[2][2] = 1;
}