#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <sstream>

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

typedef long long ll;
const int mod = 666013;

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

int main() {
    ll K;
    in>>K;

    ll mat[3][3],start[3][3];

    mat[1][1] = 0;
    mat[1][2]=mat[2][1]=mat[2][2] = 1;
    pw(mat,K);

    /*
    for (int i=1;i<=2;++i) {
        for (int j=1;j<=2;++j) {
            cout<<mat[i][j]<<' ';
        }
        cout<<'\n';
    }
    */

    start[1][1]=start[1][2]=start[2][2] = 0;
    start[2][1] = 1;
    prod(mat,start);

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

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

void prod(ll a[3][3],ll b[3][3]) {
    ll ans[3][3];
    ans[1][1]=ans[2][2]=ans[1][2]=ans[2][1]=0;

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

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

    while (exp) {
        if (exp & 1) {
            prod(ans,mat);
        }
        prod(mat,mat);
        exp >>= 1;
    }

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