#include <iostream>
//#include <iostream>
#define MOD 666013
using namespace std;

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

typedef long long int big;
struct Mat {
    big mat[2][2];
    Mat(big mat00, big mat01, big mat10, big mat11) {
        mat[0][0] = mat00 % MOD;
        mat[0][1] = mat01 % MOD;
        mat[1][0] = mat10 % MOD;
        mat[1][1] = mat11 % MOD;
    }
};

const Mat unitMat = Mat(1, 0, 0, 1);
const Mat initMat = Mat(1, 1, 1, 0);
int k;
Mat multiply(Mat a, Mat b) {
    return Mat(a.mat[0][0]*b.mat[0][0] + a.mat[0][1]*b.mat[1][0],
               a.mat[0][0]*b.mat[0][1] + a.mat[0][1]*b.mat[1][1],
               a.mat[1][0]*b.mat[0][0] + a.mat[1][1]*b.mat[1][0],
               a.mat[1][0]*b.mat[0][1] + a.mat[1][1]*b.mat[1][1]);
}
Mat pow(Mat mat, big n) {
    if (!n)
        return unitMat;
    if (n & 1)
        return multiply(mat, pow(multiply(mat, mat), n >> 1));
    return pow(multiply(mat, mat), n >> 1);
}
int main() {
    FILE *fin, *fout;
    fin = fopen("kfib.in", "r");
    fout = fopen("kfib.out", "w");
    fscanf(fin, "%lld", &k);
    fprintf(fout, "%lld", pow(initMat, k).mat[0][1]);
    return 0;
}