#include <fstream>

#define MOD 666013

using namespace std;

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

inline void mult (int a[][3], int b[][3]);

inline void logPow (int a[][3], int power);

int k;

int m[3][3];

int ans[3][3];

int main()
{
    in>>k;
    m[1][1]=1;
    m[1][2]=1;
    m[2][1]=1;
    m[2][2]=0;
    ans[1][1]=1;
    ans[1][2]=0;
    logPow(m, k-2);
    mult (ans, m);
    out<<ans[1][1];
    return 0;
}

inline void mult (int a[][3], int b[][3])
{
    int aux[3][3];
    for (register int i=1; i<=2; ++i)
        for (register int j=1; j<=2; ++j)
            aux[i][j]=0;
    for (register int i=1; i<=2; ++i)
        for (register int j=1; j<=2; ++j)
            for (register int y=1; y<=2; ++y)
                aux[i][j]=(aux[i][j]+1ll*a[i][y]*b[y][j])%MOD;
    for (register int i=1; i<=2; ++i)
        for (register int j=1; j<=2; ++j)
            a[i][j]=aux[i][j];
}

inline void logPow (int a[][3], int power)
{
    int aux[3][3];
    for (register int i=1; i<=2; ++i)
        for (register int j=1; j<=2; ++j)
            aux[i][j]=a[i][j];
    for (register int i=0; (1<<i)<=power; ++i)
    {
        if (power&(1<<i))
            mult (a, aux);
        mult (aux, aux);
    }
}