//https://infoarena.ro/problema/kfib

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define MOD 666013

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

// matrix used for multiplication in order to obtain the k-th fibonacci term
vector < vector <int> > Zmatrix = {
    {0, 1},
    {1, 1}
};
// const int Zmatrix[2][2] = {
//     {0, 1},
//     {1, 1}
// };

vector < vector <int> > myIdentity = {
    {1, 0},
    {0, 1}
};
// const int identity[2][2] = {
//     {1, 0}, 
//     {0, 1}
// };

vector < vector <int> > multiply_matrices(vector < vector <int> > &mat1, vector < vector <int> > &mat2)
{
    int n = mat1.size();
    vector < vector <int> > result(n, vector<int>(n, 0));
    
    for (int i = 0; i < n; ++i)
        for (int k = 0; k < n; ++k)
            for (int j = 0; j < n; ++j)
                result[i][j] = (result[i][j] + (1LL * mat1[i][k] * mat2[k][j]) % MOD) % MOD; // 1LL for typecast to long long to avoid overflow

    return result;
}

vector < vector <int> > exponentiate_matrix(vector < vector <int> > mat, int pow) // raise the matrix mat to the power pow
{
    if (pow == 0)
        return myIdentity; // identitiy matrix

    vector < vector <int> > m2 = multiply_matrices(mat, mat); //mat squared
    if (pow % 2) { //odd power
        vector < vector <int> > aux = exponentiate_matrix(m2, (pow - 1) / 2);
        return (multiply_matrices (mat, aux)); //mat * exponentiate_matrix(m2, (pow - 1) / 2)
    }
    else { //even power
        return exponentiate_matrix(m2, pow / 2);
    }
}

int main(){
    unsigned k;

    fin >> k;

    vector < vector <int> > fib = exponentiate_matrix(Zmatrix, k);

    fout << fib[0][1];

    // for(int i = 0; i < aux.size(); i++) {
    //     for(int j = 0; j < aux[i].size(); j++)
    //         cout << aux[i][j] << " ";
    //     cout << "\n";
    // }

    fin.close();
    fout.close();

    return 0;
}