#include <bits/stdc++.h>
using namespace std;

const int MOD = 666013;

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

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

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

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

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

Mat pwr(Mat mat, int n) {
    if (!n)
        return nullMat;
    if (n % 2)
        return prod(mat, pwr(prod(mat, mat), n / 2));
    return pwr(prod(mat, mat), n / 2);
}

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