//  Exponentiere logaritmica pe matrice - O(D^3*logN)

#include <fstream>
#include <cstring>
#define X 666013
#define D 3
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

int K,Z[D][D];

void Multiplication(const int A[][D],const int B[][D],int C[][D])
{
    int aux[D][D];
    memset(aux,0,sizeof(aux));
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
        {
            unsigned long long S=0;
            for(int k=1;k<=2;++k) S+=1LL*A[i][k]*B[k][j];
            aux[i][j]=1LL*S % X;
        }
    memcpy(C,aux,sizeof(aux));
}

void MatrixPower(int Z[][D],int K)
{
    int aux[D][D];
    memset(aux,0,sizeof(aux));
    for(int i=1;i<=2;++i)aux[i][i]=1; // aux=I
    while(K!=1)
        if(K % 2==0)Multiplication(Z,Z,Z),K/=2;
               else Multiplication(aux,Z,aux),--K;
    Multiplication(Z,aux,Z);
}

int main()
{
    f>>K;
    Z[1][1]=0,Z[1][2]=1;
    Z[2][1]=1,Z[2][2]=1;
    MatrixPower(Z,K-1);
    g<<Z[2][2]<<'\n';
    return 0;
}