#include <fstream>
#include <cstring>

using namespace std;

const int MOD = 666013;

class Matrix {
public:
    long long a[2][2];
    Matrix() {
        memset(this->a, 0, sizeof(this->a));
    }

    Matrix(int other[][2]) {
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                this->a[i][j] = other[i][j];
            }
        }
    }

    Matrix operator *(const Matrix& other) {
        Matrix ans;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 2; ++k) {
                    ans.a[i][j] = (ans.a[i][j] + this->a[i][k] * other.a[k][j]) % MOD;
                }
            }
        }
        return ans;
    }

};

int MyPow(int k, Matrix& p, Matrix& q) {
    for (; k; k >>= 1) {
        if (k & 1) {
            p = p * q;
        }
        q = q * q;
    }
    return p.a[1][1];
}

int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");

    int identity_matrix[2][2] = {1, 0, 0, 1};
    int step_matrix[2][2] = {0, 1, 1, 1};

    Matrix p(identity_matrix);
    Matrix q(step_matrix);

    int k;
    fin >> k;
    fout << MyPow(k - 1, p, q) << "\n";

    return 0;
}