#include <fstream>
using namespace std;

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

int k,imax;
int v[33];
long long A[33][4],B[4];

void biti(int n)
{
    int i,m=1;
    for(i=1;i<=30;i++)
    {
        if((m&n)==m) {v[i]=1; imax=i;}
        m=(m<<1);
    }
}

void mat(long long a1,long long a2,long long a3,long long a4,long long b1,long long b2,long long b3,long long b4,long long &c1,long long &c2,long long &c3,long long &c4)
{
    c1=(a1*b1+a2*b3)%666013;
    c2=(a1*b2+a2*b4)%666013;
    c3=(a3*b1+a4*b3)%666013;
    c4=(a3*b2+a4*b4)%666013;
}

void calc(int n)
{
    int i;
    for(i=2;i<=n;i++)
        mat(A[i-1][0],A[i-1][1],A[i-1][2],A[i-1][3],A[i-1][0],A[i-1][1],A[i-1][2],A[i-1][3],A[i][0],A[i][1],A[i][2],A[i][3]);
}

int main()
{
    int i;

    f>>k;
    biti(k-1);

    A[1][0]=0;
    A[1][1]=A[1][2]=A[1][3]=1;

    calc(imax);

    B[0]=A[imax][0];
    B[1]=A[imax][1];
    B[2]=A[imax][2];
    B[3]=A[imax][3];

    for(i=1;i<imax;i++) if(v[i]==1)
        mat(B[0],B[1],B[2],B[3],A[i][0],A[i][1],A[i][2],A[i][3],B[0],B[1],B[2],B[3]);

    g<<B[3]<<"\n";

    /*for(i=1;i<=imax;i++)
    {
        g<<i<<")\n";
        g<<A[i][0]<<"\t"<<A[i][1]<<"\n";
        g<<A[i][2]<<"\t"<<A[i][3]<<"\n";
        g<<"\n";
    }*/

    f.close();
    g.close();
    return 0;
}