#include <fstream>

using namespace std;

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

const int MOD = 666013;

struct matrix {
    long long v[2][2];

    matrix () {

        for (long long i = 0; i < 2; ++i) {
            for (long long j = 0; j < 2; ++j) {
                if (i != j) {
                    v[i][j] = 0;
                }
                else {
                    v[i][j] = 1;
                }
            }
        }

    }

    void operator = (const matrix& alpha) {

        for (long long i = 0; i < 2; ++i) {
            for (long long j = 0; j < 2; ++j) {
                v[i][j] = alpha.v[i][j];
            }
        }

    }

    void operator += (const matrix& other) {

        matrix a;

        for (long long i = 0; i < 2; ++i) {
            for (long long j = 0; j < 2; ++j) {
                a.v[i][j] = v[i][j] + other.v[i][j];
                if (a.v[i][j] >= MOD) {
                    a.v[i][j] -= MOD;
                }
            }
        }

        *this = a;

    }

    void operator *= (const matrix& other) {

        matrix a;

        for (long long i = 0; i < 2; ++i) {
            for (long long j = 0; j < 2; ++j) {
                a.v[i][j] = 0;
                for (long long k = 0; k < 2; ++k) {
                    a.v[i][j] += v[i][k] * other.v[k][j] % MOD;
                    if (a.v[i][j] >= MOD) {
                        a.v[i][j] -= MOD;
                    }
                }
            }
        }

        *this = a;

    }

    void operator ^= (long long exp) {

        matrix ans, cur;
        cur = *this;

        while (exp) {
            if (exp&1) {
                ans *= cur;
            }
            cur *= cur;
            exp>>=1;
        }

        *this = ans;

    }

};

int main()
{

    long long n;

    matrix alpha;

    cin >> n;

    alpha.v[0][0] = 0;
    alpha.v[0][1] = 1;
    alpha.v[1][0] = 1;
    alpha.v[1][1] = 1;

    alpha ^= n - 1;

    cout << alpha.v[1][1] << "\n";

    return 0;
}