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

#define MOD 666013

vector<vector<long long>> matrix_mul(vector<vector<long long>> &A, vector<vector<long long>> &B)
{
    long long n = A.size();
    vector<vector<long long>> result(n, vector<long long>(n, 0));

    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < n; k++)
        {
            long long aik = A[i][k];
            if (aik == 0)
            {
                continue;
            }
            for (int j = 0; j < n; j++)
            {
                result[i][j] = (result[i][j] + aik * B[k][j]) % MOD;
            }
        }
    }

    return result;
}

vector<vector<long long>> matrix_pow(vector<vector<long long>> &base, long long J)
{
    int n = base.size();
    vector<vector<long long>> result(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++)
    {
        result[i][i] = 1;
    }

    while (J > 0)
    {
        if (J % 2 == 1)
        {
            result = matrix_mul(result, base);
        }
        base = matrix_mul(base, base);
        J = J / 2;
    }

    return result;
}

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

    vector<vector<long long>> m(2, vector<long long>(2, 0));
    vector<vector<long long>> z(2, vector<long long>(2, 0));
    vector<vector<long long>> r(2, vector<long long>(2, 0));

    m[0][0] = 0;
    m[0][1] = 1;

    z[0][0] = 0;
    z[0][1] = 1;
    z[1][0] = 1;
    z[1][1] = 1;

    int k;
    fin >> k;

    r = matrix_pow(z, k);
    r = matrix_mul(m, r);

    fout << r[0][0] << "\n";

    return 0;
}