#include <iostream>
#include <fstream>
#include <queue>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
const int NMax = 1e3 + 5;
const int mod = 666013;

ll K;

void prod(ll a[3][3],ll b[3][3]);
void pw(ll a[3][3],ll);

int main() {
    in>>K;

    ll st[3][3] = {{0,0,0},{0,0,1},{0,1,1}};
    ll dr[3][3] = {{0,0,0},{0,0,0},{0,1,0}};

    pw(st,K);
    prod(st,dr);

    out<<st[1][1]<<'\n';

    return 0;
}

void prod(ll a[3][3],ll b[3][3]) {
    ll c[3][3] = {};

    for (int i=1;i <= 2;++i) {
        for (int j=1;j <= 2;++j) {
            for (int k=1;k <= 2;++k) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
            }
        }
    }

    for (int i=1;i <= 2;++i) {
        for (int j=1;j <= 2;++j) {
            a[i][j] = c[i][j];
        }
    }
}

void pw(ll base[3][3],ll exp) {
    ll ans[3][3] = {{0,0,0},{0,1,0},{0,0,1}};

    while (exp) {
        if (exp & 1) {
            prod(ans,base);
        }

        prod(base,base);
        exp >>= 1;
    }

    for (int i=1;i <= 2;++i) {
        for (int j=1;j <= 2;++j) {
            base[i][j] = ans[i][j];
        }
    }
}