#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int k,M[3][3],Sol[3][3];
void inmult(int A[][3],int B[][3],int C[][3])
{
    for(int i=0; i<=1;i++)
        for(int j=0; j<=1; j++)
            for(int l=0; l<=1; l++)
            C[i][j]=(C[i][j]+A[i][l]*B[l][j])%666013;
}
void rid(int k,int Sol[][3])
{
    int C[3][3],Aux[3][3];
    for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)
            C[i][j]=Sol[i][j];
    Sol[0][0]=Sol[1][1]=1;
    for(int i=1;(1<<i)<=k;i++)
    {
        if((1<<i)&k!=0)
        {
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
                Aux[i][j]=0;
        inmult(Sol,C,Aux);
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
                Sol[i][j]=Aux[i][j];
        }
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
                Aux[i][j]=0;
        inmult(C,C,Aux);
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
                C[i][j]=Aux[i][j];
    }
}
int main()
{
    fin>>k;
    M[0][0]=0;
    M[0][1]=M[1][0]=M[1][1]=1;
    rid(k-1,Sol);
    fout<<Sol[1][1];
    return 0;
}