//
//  Al k-lea termen Fibonacci.cpp
//  
//
//  Created by Raoul Bocancea on 23/11/2018.
//

#include <fstream>
#include <cstring>

const std :: string programName = "kfib";
std :: fstream f(programName, std :: ios :: in);
std :: fstream g(programName, std :: ios :: out);

void matrix_multiplication(int [][3], int [][3], int [][3]);
void lgput(int [][3], int);

const int MOD = 666013;

int N, Matrix[3][3], solution[3][3];

int main(void) {
    f >> N;
    Matrix[0][0] = 0;
    Matrix[0][1] = 1;
    Matrix[1][0] = 1;
    Matrix[1][1] = 1;
    lgput(solution, N - 1);
    g << solution[1][1];
    return 0x0;
}

void matrix_multiplication(int A[][3], int B[][3], int C[][3]) {
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
}

void lgput(int M[][3], int P) {
    int C[3][3], aux[3][3];
    memcpy(C, Matrix, sizeof Matrix); // C = Xcopy
    M[0][0] = M[1][1] = 1; // M = sol = 1
    for (int i = 0; (1 << i) <= P; ++i) {
        if ((1 << i) & P) {
            memset(aux, 0, sizeof aux);
            matrix_multiplication(M, C, aux);
            memcpy(M, aux, sizeof aux);
        }
        memset(aux, 0, sizeof aux);
        matrix_multiplication(C, C, aux);
        memcpy(C, aux, sizeof C);
    }
}