#include <fstream>

#define MOD 666013

using namespace std;

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

class matrix {
    public:
    long long a11, a12, a21, a22;
    matrix(long long _a11, long long _a12) {
        a11 = _a11;
        a12 = _a12;
    }
    matrix(char type) {
        if(type == 'F') {
            ///Fibo
            a11 = 0;
            a12 = 1;
            a21 = 1;
            a22 = 1;
        }
        if(type == 'I') {
            ///I2
            a11 = 1;
            a12 = 0;
            a21 = 0;
            a22 = 1;
        }
        if(type == 'S') {
            ///First terms
            a11 = 0;
            a12 = 1;
            a21 = 0;
            a22 = 0;
        }
    }
    matrix() {
        a11 = 0;
        a12 = 0;
        a21 = 0;
        a22 = 0;
    }
    inline matrix operator * (const matrix &other) {
        matrix ans;
        ans.a11 = (this->a11 * other.a11 + this->a12 * other.a21) % MOD;
        ans.a12 = (this->a11 * other.a12 + this->a12 * other.a22) % MOD;
        ans.a21 = (this->a21 * other.a11 + this->a22 * other.a21) % MOD;
        ans.a22 = (this->a21 * other.a12 + this->a22 * other.a22) % MOD;
        return ans;
    }

};

int term_pos, term_val;

matrix power(matrix a, int exp) {
    if(exp == 0) {
        return matrix('I');
    }
    if(exp % 2 == 0) {
        matrix temp = power(a, exp / 2);
        return temp * temp;
    }
    else {
        return power(a, exp - 1) * a;
    }
}

void read() {
    cin >> term_pos;
}

void solve() {
    term_val = (matrix('S') * power(matrix('F'), term_pos - 1) ).a12;
}

void print() {
    cout << term_val;
}

int main() {
    read();
    solve();
    print();
    return 0;
}