#include <fstream>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
long long m[5][5],k,mi[5][5],aux[5][5];
void inmultire(long long a[5][5],long long b[5][5])
{
    aux[1][1]=(a[1][1]*b[1][1]+a[1][2]*b[2][1])%666013;
    aux[1][2]=(a[1][1]*b[1][2]+a[1][2]*b[2][2])%666013;
    aux[2][1]=(a[2][1]*b[1][1]+a[2][2]*b[2][1])%666013;
    aux[2][2]=(a[2][1]*b[1][2]+a[2][2]*b[2][2])%666013;
}
void putere(long long p)
{
    if(p==1)
        return;
    putere(p/2);
    inmultire(m,m);
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
            m[i][j]=aux[i][j];
    if(p%2==1)
        inmultire(m,mi);
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
            m[i][j]=aux[i][j];
    return;
}
int main()
{
    in>>k;
    k--;
    m[1][2]=m[2][1]=m[2][2]=1;
    mi[1][2]=mi[2][1]=mi[2][2]=1;
    putere(k);
    out<<m[2][2];
    return 0;
}