#include <fstream>
#define Md 666013
#define lint long long int

using namespace std;

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

lint mat[3][3],n;

void Inm(lint a[][3],lint b[][3])
{
    lint c[3][3];
    c[0][0]=c[1][1]=c[0][1]=c[1][0]=0;

    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j)
            for(int k=0;k<2;++k)
                c[i][j]=(c[i][j]+(a[i][k]*b[k][j]%Md))%Md;

    a[0][0]=c[0][0];
    a[0][1]=c[0][1];
    a[1][0]=c[1][0];
    a[1][1]=c[1][1];
}

void RidPt(lint ba[][3],int ex)
{
    lint A[3][3];
    A[0][0]=A[1][1]=1;
    A[0][1]=A[1][0]=0;

    while(ex)
    {
        if(ex&1)
            Inm(A,ba);

        ex>>=1;
        Inm(ba,ba);
    }

    ba[0][0]=A[0][0];
    ba[0][1]=A[0][1];
    ba[1][0]=A[1][0];
    ba[1][1]=A[1][1];
}

int main()
{
    mat[1][0]=mat[0][1]=mat[1][1]=1;

    cin>>n;

    RidPt(mat,n-1);

    cout<<mat[1][1];

    return 0;
}