#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

#define MOD 666013

int p;
int mat[3][3] ={{ 0, 1},{ 1, 1}};
int sol[3][3] ={{ 1, 0},{ 0, 1}};
int aux[3][3];

void inmultire (int A[][3], int B[][3])
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                aux[i][j]+= (1LL * A[i][k] * B[k][j])%MOD;
}

int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    fin>>p;
    p--;
    for(int k=0;1<<k<=p;k++){
        if((1<<k)&p){
            memset(aux,0,sizeof(aux));
            inmultire(mat,sol);
            memcpy(sol,aux,sizeof(aux));
        }
        memset(aux,0,sizeof(aux));
        inmultire(mat,mat);
        memcpy(mat,aux,sizeof(aux));
    }
    fout<<sol[1][1]<<'\n';
    return 0;
}