#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int modulo = 666013;
int mat[2][2];
void exponentiere_rapida(int mat[2][2], int n) {
    if (n == 0){
        for (int i = 0; i <= 1; i++){
            for (int j = 0; j <= 1; j++){
                mat[i][j] = (i == j);
            }
        }
    } else if (n % 2 == 0){
        int aux[2][2];
        exponentiere_rapida(mat, n / 2);
        for (int i = 0; i <= 1; i++){
            for (int j = 0; j <= 1; j++){
                aux[i][j] = mat[i][j] % modulo;
            }
        }
        for (int i = 0; i <= 1; i++){
            for (int j = 0; j <= 1; j++){
                mat[i][j] = 0;
                for (int k = 0; k <= 1; k++)
                    mat[i][j] = (1LL * mat[i][j] + (1LL * aux[i][k] * aux[k][j])) % modulo;
            }
        }
    } else {
        int init[2][2];
        int aux[2][2];
        init[0][0] = 0;
        init[0][1] = 1;
        init[1][0] = 1;
        init[1][1] = 1;
        exponentiere_rapida(mat, n - 1);
        for (int i = 0; i <= 1; i++) {
            for (int j = 0; j <= 1; j++) {
                aux[i][j] = mat[i][j];
            }
        }
        for (int i = 0; i <= 1; i++){
            for (int j = 0; j <= 1; j++){
                mat[i][j] = 0;
                for (int k = 0; k <= 1; k++)
                    mat[i][j] = (1LL * mat[i][j] + (1LL * aux[i][k] * init[k][j])) % modulo;
            }
        }
    }
}
int main(){
    int k;
    fin >> k;
    exponentiere_rapida(mat, k);
    fout << mat[1][0];
    return 0;
}