#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;

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

struct matrix {
    long long m[2][2];
    matrix operator*(const matrix &x) {
        matrix temp;
        int cnt = 0;
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 2; j++) {
                for(int k = 0; k < 2; k++)
                    if(cnt == 0)
                        temp.m[i][j] = m[i][cnt]*x.m[cnt++][j];
                    else
                        temp.m[i][j] += m[i][cnt]*x.m[cnt++][j];
                temp.m[i][j] %= MOD;
                cnt = 0;
            }
        }
        return temp;
    }
};

matrix lgpow(matrix st, int pw, matrix init) {
    if(pw == 1)
        return init;
    if(pw == 2)
        return st*init;
    if(pw%2 == 0) {
        matrix t = lgpow(st, pw/2, init);
        return t*t;
    } else {
        return lgpow(st, pw-1, init)*init;
    }
}

int main() {

    int n;
    in >> n;

    if(n == 1 || n == 2) {
        out << 1;
        return 0;
    }

    matrix mt2;
    mt2.m[0][0] = 1;
    mt2.m[0][1] = 1;
    mt2.m[1][0] = 0;
    mt2.m[1][1] = 0;

    matrix mt;
    mt.m[0][0] = 0;
    mt.m[0][1] = 1;
    mt.m[1][0] = 1;
    mt.m[1][1] = 1;

    mt = lgpow(mt, n-2, mt);
    mt = mt2*mt;

    out << mt.m[0][1]%MOD;

    return 0;
}