#include <stdio.h>

#define MOD 666013

// Functie auxiliara pentru a inmulti doua matrici 2x2 cu reducere modulara
void inmultire(long long a[2][2], long long b[2][2], long long rez[2][2]) {
    long long temp[2][2] = {0};
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            for(int k = 0; k < 2; k++) {
                temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    // Copiem rezultatul in matricea destinatie
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            rez[i][j] = temp[i][j];
        }
    }
}

int main() {
    FILE *fin = fopen("kfib.in", "r");
    FILE *fout = fopen("kfib.out", "w");
    long long k;
    fscanf(fin, "%lld", &k);
    
    long long z[2][2] = {{0, 1}, {1, 1}}; // Matricea de transformare
    long long r[2][2] = {{1, 0}, {0, 1}}; // Matricea identitate
    
    long long p = k - 1;
    if (k == 0) {
        fprintf(fout, "0\n");
    } else {
        // Ridicarea matricii la puterea (K-1)
        while(p > 0) {
            if(p % 2 == 1) inmultire(r, z, r);
            inmultire(z, z, z);
            p /= 2;
        }
        fprintf(fout, "%lld\n", r[1][1]);
    }
    
    fclose(fin);
    fclose(fout);
    return 0;
}