#include <fstream>
#define MOD 666013

std::ifstream fin("kfib.in");
std::ofstream fout("kfib.out");

struct Mat {
    long long int mat[2][2];
};

const Mat nullMat = {
    {{1, 0},
     {0, 1}}
};

const Mat initMat = {
    {{1, 1},
     {1, 0}}
};

int k;

Mat prod(Mat a, Mat b) {
    Mat ret;
    ret.mat[0][0] = (a.mat[0][0] * b.mat[0][0] + a.mat[0][1] * b.mat[1][0]) % MOD;
    ret.mat[0][1] = (a.mat[0][0] * b.mat[0][1] + a.mat[0][1] * b.mat[1][1]) % MOD;
    ret.mat[1][0] = (a.mat[1][0] * b.mat[0][0] + a.mat[1][1] * b.mat[1][0]) % MOD;
    ret.mat[1][1] = (a.mat[1][0] * b.mat[0][1] + a.mat[1][1] * b.mat[1][1]) % MOD;
    return ret;
}

Mat pow(Mat mat, int n) {
    if (!n)
        return nullMat;

    if (n & 1) // n % 2
        return prod(mat, pow(prod(mat, mat), n >> 1));
    return pow(prod(mat, mat), n >> 1);
}

int main() {
    fin >> k;
    fout << pow(initMat, k).mat[0][1] << '\n';

    fout.close();
    return 0;
}