#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
const int mod = 666013;
struct mat{
    int m[2][2];
};
mat nullMat = {
    {{1, 0},
     {0, 1}}
};
mat matrice{
    {{0, 1}, 
    {1, 1}}
};
int n;
mat produs(mat a, mat b){
    mat c;
    c.m[0][0] = (1LL * a.m[0][0] * b.m[0][0] + 1LL * a.m[0][1] * b.m[1][0]) % mod;
    c.m[0][1] = (1ll * a.m[0][0] * b.m[0][1] + 1ll * a.m[0][1] * b.m[1][1]) % mod;
    c.m[1][0] = (1ll * a.m[1][0] * b.m[0][0] + 1ll * a.m[1][1] * b.m[1][0]) % mod;
    c.m[1][1] = (1ll * a.m[1][0] * b.m[0][1] + 1ll * a.m[1][1] * b.m[1][1]) % mod;
    return c;
}
mat exponentiere(mat a, int n){
    if(n == 0) return nullMat;
    else {
        mat nr = exponentiere(a, n / 2);
        if(n % 2 == 1){
            return produs(a, produs(nr, nr));
        }
        else{
            return produs(nr, nr);
        }
    }
}
int main(){
    f >> n;
    g << exponentiere(matrice, n).m[0][1];
}