#include <iostream>
#include<bits/stdc++.h>

using namespace std;

vector<vector<long long>> mat_mult(vector<vector<long long>> a, vector<vector<long long>> b)
{
    vector<vector<long long>> res{{0,0}, {0,0}};

    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < a[i].size(); j++) {
            for (int k = 0; k < a[i].size(); k++)
                res[i][j] += a[i][k]*b[k][j];
        }
    }

    return res;
}

vector<vector<long long>> mat_mod(vector<vector<long long>> a)
{
    for (int i = 0; i < a.size(); i++)
        for (int j = 0; j < a[i].size(); j++)
            a[i][j] = a[i][j]%666013;

    return a;
}

vector<vector<long long>> mat_pow(vector<vector<long long>> a, long long k)
{
    if (k == 0) return {{1,0}, {0,1}};
    if (k%2==0) return mat_pow(mat_mod(mat_mult(a, a)), k/2);
    return mat_mod(mat_mult(a, mat_mod(mat_pow(mat_mod(mat_mult(a, a)), k/2))));
}

int main()
{

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

    int k;
    vector<vector<long long>> a = {{0, 1}, {1, 1}};

    fin>>k;
    vector<vector<long long>> res = mat_pow(a, k-1);

    fout<<res[0][0] + res[1][0]<<'\n';
    return 0;
}