#include <iostream>
#include <fstream>
#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>

#define ll long long
#define ull unsigned long long
#define pb push_back
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");

const int NMax = 1e5 + 5;
const ll inf = 1e18 + 5;
const int mod = 666013;

int K;

void pw(ll[3][3],int);
int prod(ll[3][3],ll[3][3]);

int main() {
    in>>K;

    ll ans[3][3] = {0,0,0,0,0,1,0,1,1}, st[3][3] = {0,0,0,0,0,0,0,1,0};
    pw(ans,K);
    prod(ans,st);

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

    in.close();out.close();
    return 0;
}

void pw(ll base[3][3],int 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];
        }
    }
}

int prod(ll a[3][3],ll b[3][3]) {
    ll m[3][3] = {};

    for (int i=1;i <= 2;++i) {
        for (int j=1;j <= 2;++j) {
            //m[i][j] = 0;
            for (int k=1;k <= 2;++k) {
                m[i][j] = (m[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] = m[i][j];
        }
    }
}