#include <iostream>
#include <fstream>
#include <array>

using namespace std;

typedef array < array < int , 2 > , 2 > vvi;

const int MOD = 666013;

vvi mult(vvi a, vvi b)
{
    vvi ret;
    ret[0][0] = ((1LL * a[0][0] * b[0][0]) % MOD + (1LL * a[0][1] * b[1][0]) % MOD) % MOD;
    ret[0][1] = ((1LL * a[0][0] * b[0][1]) % MOD + (1LL * a[0][1] * b[1][1]) % MOD) % MOD;
    ret[1][0] = ((1LL * a[1][0] * b[0][0]) % MOD + (1LL * a[1][1] * b[1][0]) % MOD) % MOD;
    ret[1][1] = ((1LL * a[1][0] * b[0][1]) % MOD + (1LL * a[1][1] * b[1][1]) % MOD) % MOD;

    return ret;
}

vvi expo(vvi base, int exp)
{
    vvi ret;
    if(exp == 0)
    {
        ret[0][0] = ret[1][1] = 1;
        ret[0][1] = ret[1][0] = 0;
        return ret;
    }
    else if(exp == 1)
    {
        return base;
    }

    vvi tmp = expo(base, exp / 2);
    ret = mult(tmp, tmp);
    if(exp % 2)
    {
        ret = mult(ret, base);
    }

    return ret;
}

int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    int k; f >> k;

    vvi mat;
    mat[0][0] = 0;
    mat[0][1] = mat[1][0] = mat[1][1] = 1;

    vvi ans = expo(mat, k - 1);

    g << ans[1][1] << '\n';

    f.close();
    g.close();
    return 0;
}