#include <iostream>
#include <fstream>
#include <cstring>
#define m 666013
using namespace std;

typedef int lg;
lg k;
lg z[3][3];
lg sol[3][3];

inline void inm(lg a[][3], lg b[][3], lg c[][3])
{
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j){
            c[i][j] = 0;
            for(int k=1;k<=2;++k)
            {
                c[i][j] = (c[i][j] +1LL*a[i][k]*b[k][j])%m;
            }
        }
}

inline void pw(lg a[3][3], lg n)
{
    lg c[3][3], i, aux[3][3];
    a[1][1] = a[2][2] = 1;
    memcpy(c, z, sizeof(z));
    for(i=0;(1<<i)<=n;++i)
    {
        if(n&(1<<i))
        {
            memset(aux, 0, sizeof(aux));
            inm(a,c,aux);
            memcpy(a, aux, sizeof(aux));
        }
        memset(aux, 0, sizeof(aux));
        inm(c, c, aux);
        memcpy(c, aux, sizeof(aux));
    }
}

int main()
{

    ifstream in("kfib.in");
    in >> k;
    in.close();
    z[1][1] = 0;
    z[1][2] = z[2][1] = z[2][2] = 1;

    pw(sol, k-1);
    ofstream out("kfib.out");
    out << sol[2][2];
    out.close();
    return 0;
}