#include <bits/stdc++.h>
#define mod 666013
#define ll long long

using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");

int k;

void mul(ll a[2][2], ll b[2][2]){
    ll p[2][2];
    memset(p, 0, sizeof p);
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++){
                p[i][j] += a[i][k] * b[k][j];
                p[i][j] %= mod;
            }
    memcpy(a, p, sizeof p);
}

ll lg(int k){
    if(k < 2)
        return k;
    k--;
    ll mat[2][2] = {0, 1, 1, 1};
    ll aux[2][2] = {0, 1, 1, 1};
    while(k){
        if(k & 1)
            mul(mat, aux);
        mul(aux, aux);
        k >>= 1;
    }
    return mat[1][0];
}

int main(){
    in >> k;
    out << lg(k);
    return 0;
}