#include <fstream>
#include <vector>
using namespace std;

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

const int MOD = 666013;

class Matrix{

private:
    vector<vector<int> > values;

public:
    Matrix () {}
    Matrix (int SIZE)
    {
        values = vector<vector<int>> (SIZE, vector<int> (SIZE));
    }
    void Set (int x, int y, int val)
    {
        values[x-1][y-1] = val;
    }
    int Get(int i, int j)
    {
        return this->values[i][j];
    }
    Matrix operator*(const Matrix& B)
    {
        size_t i, j, k;
        Matrix aux(B.values.size());
        for (i = 0; i < B.values.size(); ++i)
            for (j = 0; j < B.values.size(); ++j)
                for (k = 0; k < B.values.size(); ++k)
                    aux.Set(i+1, j+1, (( 1LL * aux.Get(i, j) + 1LL * this->values[i][k] * B.values[k][j] ) % MOD));
        return aux;
    }
};

int N;
Matrix Z;

Matrix MatrixLpow(Matrix A, int B);

int main()
{
    is >> N;
    Matrix Z(2);

    Z.Set(1, 2, 1);
    Z.Set(2, 1, 1);
    Z.Set(2, 2, 1);

    os << MatrixLpow(Z, N+1).Get(0, 0);

    is.close();
    os.close();
}

Matrix MatrixLpow(Matrix A, int B)
{
    if (B == 0) return Z;
    if (B == 1) return A;
    if (B % 2 == 0) return MatrixLpow(A * A, B/2);
    if (B % 2 == 1) return (A * MatrixLpow(A * A, B/2));
};