/**
 * user: caen1
 * file: infoarena/kfib.c
 * date: 24 apr 2011
**/
#include <stdio.h>

#define IN "kfib.in"
#define OUT "kfib.out"
#define MOD 666013
#define PER 1332028

int main(void) {

    long k, x = 0, y = 1, z;

    (void) freopen(IN, "r", stdin);
    (void) freopen(OUT, "w", stdout);

    (void) scanf("%ld", &k);

    while(k-- % PER) z = (x + y) % MOD, x = y, y = z;

    printf("%ld\n", x);

    return 0;
}