#include <fstream>
using namespace std;
int k,m[2][2],sol[2][2];
inline void ridica(int k,int M[][2])
{
    int C[2][2],aux[2][2];
    C[0][0]=m[0][0]; C[1][1]=m[1][1]; C[0][1]=m[0][1]; C[1][0]=m[1][0];
    M[0][0]=M[1][1]=1;
    for (int l=0;(1<<l)<=k;l++)
      { if (k&(1<<l))
        {
            aux[0][0]=aux[0][1]=aux[1][0]=aux[1][1]=0;
            for (int i=0;i<2;i++)
                for (int j=0;j<2;j++)
                    for (int k=0;k<2;k++)
                        aux[i][j]=(aux[i][j]+1LL*M[i][k]*C[k][j])%666013;
            M[0][0]=aux[0][0];
            M[0][1]=aux[0][1];
            M[1][0]=aux[1][0];
            M[1][1]=aux[1][1];
        }
        aux[0][0]=aux[0][1]=aux[1][0]=aux[1][1]=0;
        for (int i=0;i<2;i++)
            for (int j=0;j<2;j++)
                for (int k=0;k<2;k++)
                    aux[i][j]=(aux[i][j]+1LL*C[i][k]*C[k][j])%666013;
        C[0][0]=aux[0][0];
        C[0][1]=aux[0][1];
        C[1][0]=aux[1][0];
        C[1][1]=aux[1][1];
      }

}
int main(void)
{
    ifstream f("kfib.in");
    ofstream o("kfib.out");
    f>>k;
    m[0][0]=0; m[0][1]=1; m[1][0]=1; m[1][1]=1;
    ridica(k-1,sol);
    o<<sol[1][1];
}