#include <fstream>
#include <vector>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long k;
vector<vector<long long>> multiply(vector<vector<long long>> mat1, vector<vector<long long>> mat2) {
    int N = mat1.size();
    int M = mat2[0].size();
    vector<vector<long long>> rasp;
    vector<long long> aux;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            long long s = 0;
            for (int a = 0; a < mat2.size(); ++a) {
                s += mat1[i][a] * mat2[a][j];
                s = s % MOD;
            }
            aux.push_back(s);
        }
        rasp.push_back(aux);
        aux.clear();
    }
    return rasp;
}
vector<vector<long long>> power(vector<vector<long long>> a, long b) {
    vector<vector<long long>> p;
    vector<long long> aux;
    for (int i = 0; i < a.size(); ++i) {
        for (int j = 0; j < a[i].size(); ++j) {
            if (i == j) {
                aux.push_back(1);
            }
            else {
                aux.push_back(0);
            }
        }
        p.push_back(aux);
        aux.clear();
    }
    while (b) {
        if (b & 1) {
            p = multiply(p, a);
        }
        a = multiply(a, a);
        b /= 2;
    }
    return p;
}
int main()
{
    fin >> k;
    vector<vector<long long>> matTrecere, first;
    vector<long long> aux;
    aux.push_back(0); aux.push_back(1);
    matTrecere.push_back(aux); aux.clear();
    aux.push_back(1); aux.push_back(1);
    matTrecere.push_back(aux);
    first.push_back(aux);
    matTrecere = power(matTrecere, k - 1);
    first = multiply(first, matTrecere);
    fout << first[0][0] << "\n";
    return 0;
}