#include <bits/stdc++.h>
using namespace std;

#define MOD 666013
typedef long long ll;
typedef vector<vector<ll>> vvi;
ifstream in("kfib.in");
ofstream out("kfib.out");

vvi mult_mat(const vvi &a, const vvi &b)
{
    vvi z;
    z.push_back({(a[0][0]*b[0][0]+a[0][1]*b[1][0])%MOD, (a[0][0]*b[0][1]+a[0][1]*b[1][1])%MOD});
    z.push_back({(a[1][0]*b[0][0]+a[1][1]*b[1][0])%MOD, (a[1][0]*b[0][1]+a[1][1]*b[1][1])%MOD});
    return z;
}

vvi exp_mat(vvi x, int n)
{
    if(n == 0) return {{1, 0}, {0, 1}};
    else
    {
        vvi E = mult_mat(x, x);
        E[0][0] %= MOD;
        E[0][1] %= MOD;
        E[1][0] %= MOD;
        E[1][1] %= MOD;

        if(n%2 == 0)
            return exp_mat(E, n/2);

        vvi E1 = mult_mat(x, exp_mat(E, n/2));
        E1[0][0] %= MOD;
        E1[0][1] %= MOD;
        E1[1][0] %= MOD;
        E1[1][1] %= MOD;

        return E1;
    }
}

int main()
{
    int k;
    in >> k;

    vvi M, Z;
    M.push_back({0, 1});
    Z.push_back({0, 1});
    Z.push_back({1, 1});

    Z = exp_mat(Z, k-1);

    out << Z[1][1];

    return 0;
}