#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;

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

void inmultire(long long a[2][2], long long b[2][2], long long rez[2][2]){
    rez[0][0] = (a[0][0]*b[0][0] % MOD + a[0][1] * b[1][0] % MOD)%MOD;
    rez[0][1] = (a[0][0]*b[0][1]%MOD + a[0][1]*b[1][1]%MOD)%MOD;
    rez[1][0] = (a[1][0]*b[0][0]%MOD + a[1][1]*b[1][0]%MOD)%MOD;
    rez[1][1] = (a[1][0]*b[0][1]%MOD + a[1][1]*b[1][1]%MOD)%MOD;
}

void ridicare(long long a[2][2], long long put, long long rez[2][2]){
    if(put==0)
    {
        rez[0][0] = 1,rez[0][1] = 0,rez[1][0] = 0, rez[1][1] = 1;
        return;
    }
    if(put%2==1){
        long long aux[2][2];
        ridicare(a, put-1, aux);
        inmultire(a, aux, rez);
        return;
    }
    long long aux[2][2];
    ridicare(a, put/2, aux);
    inmultire(aux, aux, rez);
}

int kfib(int k){
    long long a[2][2]={{1, 1},{1, 0}};
    long long aux[2][2];
    ridicare(a, k-1, aux);

    return aux[0][0];
}

int main(){
    long long k;
    fin>>k;
    fout<<kfib(k);
}