//  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)
            for(int k=1;k<=2;++k)
                aux[i][j]=(aux[i][j]+1LL*A[i][k]*B[k][j]) % X;
    memcpy(C,aux,sizeof(aux));
}

void MatrixPower(int Z[][D],int K)
{
    int aux[D][D];
    aux[1][1]=1,aux[1][2]=0;  // aux=I
    aux[2][1]=0,aux[2][2]=1;
    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;
}