#include <fstream>
#include <cstring>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

int K, Z[2][2];

void inmultire(const int A[][2], const int B[][2], int C[][2])
{
    int aux[2][2];
    memset(aux, 0, sizeof(aux));
    for (int i=0; i<2; ++i)
        for (int j=0; j<2; ++j)
        {
            long long sum=0;
            for  (int k=0; k<2; ++k)
                sum+=1LL*A[i][k]*B[k][j];
            aux[i][j]=(1LL*sum%mod);
        }
    memcpy(C, aux, sizeof(aux));
}

void log_pow(int Z[][2], int K)
{
    int res[2][2];
    memset(res, 0, sizeof(res));
    res[0][0]=res[1][1]=1;
    while (K)
    {
        if (K%2) inmultire(Z, res, res);
        inmultire(Z, Z, Z); K/=2;
    }
    memcpy(Z, res, sizeof(res));
}

int main()
{
    f>>K;
    Z[0][0]=0; Z[0][1]=1;
    Z[1][0]=1; Z[1][1]=1;
    log_pow(Z, K-1);
    g<<Z[1][1]<<'\n';
    return 0;
}