//  Exponentiere logaritmica pe matrice - O(Dim^3*logN)
#include <fstream>
#include <cstring>
#define X 666013
#define Dim 5
#define D 2
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

int K,Z[Dim][Dim],aux[Dim][Dim];

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

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

void Show(int Z[][Dim])
{
     for(int i=1;i<=D;++i,g<<'\n')
        for(int j=1;j<=D;++j)g<<Z[i][j]<<' ';
}
int main()
{
    f>>K;
    Z[1][1]=0,Z[1][2]=1;
    Z[2][1]=1,Z[2][2]=1;
    MatrixPower(Z,K-1);
    //Show(Z);
    g<<(Z[2][2]) % X <<'\n';
    return 0;
}