#include <iostream>
#include <cstdint>
#include <cmath>
#include <stdio.h>

using namespace std;
typedef long long ll;
void rezultat(ll** z){
   cout << (1*z[1][2] + 2*z[2][2]) % 666013;
}

ll ** inmultire_matrici(ll **z, ll **x){
    ll** A = (ll**)malloc(2*sizeof(ll*));
    A[1] = (ll*)malloc(2*sizeof(ll));
    A[2] = (ll*)malloc(2*sizeof(ll));

    A[1][1] = (z[1][1]*x[1][1]% 666013 + z[1][2]*x[2][1]% 666013) % 666013;
    A[1][2] = (z[1][1]*x[1][2]% 666013 + z[1][2]*x[2][2]% 666013) % 666013;
    A[2][1] = (z[2][1]*x[1][1]% 666013 + z[2][2]*x[2][1]% 666013) % 666013;
    A[2][2] = (z[2][1]*x[1][2]% 666013 + z[2][2]*x[2][2]% 666013) % 666013;

    return A;
}

ll ** exponentiere(ll **z, ll P){
    ll** A = (ll**)malloc(2*sizeof(ll*));
    A[1] = (ll*)malloc(2*sizeof(ll));
    A[2] = (ll*)malloc(2*sizeof(ll));


    if(P == 1){
        return z;
    }

    if(P%2 == 0){
        A = inmultire_matrici(z, z);
        return exponentiere(A, P/2);
    }
    else
    {
        A = inmultire_matrici(z, z);
        return inmultire_matrici(exponentiere(A, (P-1)/2), z);
    }
}

int main(){
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    ll** z = (ll**)malloc(2*sizeof(ll*));

    z[1] = (ll*)malloc(2*sizeof(ll));
    z[2] = (ll*)malloc(2*sizeof(ll));

    z[1][1] = 0;
    z[1][2] = 1;
    z[2][1] = 1;
    z[2][2] = 1;

    ll N;
    cin >> N;

    ll** A = (ll**)malloc(2*sizeof(ll*));

    A[1] = (ll*)malloc(2*sizeof(ll));
    A[2] = (ll*)malloc(2*sizeof(ll));

    if(N == 3)
        cout << 2;
    else
        if(N == 0)
            cout << 0;
        else
            if(N == 2 || N == 1)
                cout << 1;
            else{
                A = exponentiere(z, N-3);
                rezultat(A);
            }

    return 0;
}