#include <iostream>
#define mod 666013
#include <fstream>
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int init[3][3] , mat[3][3] , k , kfib;

void matmult(int a[][3] , int b[][3]){
    int c[3][3];
    c[1][1]=(1LL*a[1][1]*b[1][1])%mod + (1LL*a[1][2]*b[2][1])%mod;
    c[1][2]=(1LL*a[1][1]*b[1][2])%mod + (1LL*a[1][2]*b[2][2])%mod;
    c[2][1]=(1LL*a[2][1]*b[1][1])%mod + (1LL*a[2][2]*b[2][1])%mod;
    c[2][2]=(1LL*a[2][1]*b[1][2])%mod + (1LL*a[2][2]*b[2][2])%mod;
    for(int i=1 ; i<=2 ; i++)
        for(int j=1 ; j<=2 ; j++)
            a[i][j]=c[i][j];
}


void power(int a[][3] , int k){
    if(k == 1){
        return;
    }
    else if(k%2==0){
        power(a , k/2);
        matmult(a , a);
    }
    else if(k%2==1){
        power(a , k/2);
        matmult(a , a);
        matmult(a , init);
    }
}

int main()
{
    fin>>k;
    init[1][1]=mat[1][1]=0;
    init[1][2]=mat[1][2]=mat[2][1]=init[2][1]=mat[2][2]=init[2][2]=1;
    if(k == 0){
        fout<<0;
    }
    else if((k == 1)||(k == 2)){
        fout<<1;
    }
    else if(k > 2){
        k--;
        power(mat , k);
        kfib=mat[2][2]%mod;
        fout<<kfib;
    }
    return 0;
}