#include <bits/stdc++.h>

using namespace std;

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

const int mod = 666013;

long long mat[4][4], aux[4][4], prod[4][4];

void self_multiply(){
    aux[1][1] = (mat[1][1]*mat[1][1] + mat[1][2]*mat[2][1])%mod;
    aux[1][2] = (mat[1][1]*mat[1][2] + mat[1][2]*mat[2][2])%mod;
    aux[2][1] = (mat[2][1]*mat[1][1] + mat[2][2]*mat[2][1])%mod;
    aux[2][2] = (mat[2][1]*mat[1][2] + mat[2][2]*mat[2][2])%mod;
    mat[1][1] = aux[1][1];
    mat[1][2] = aux[1][2];
    mat[2][1] = aux[2][1];
    mat[2][2] = aux[2][2];
}

void prod_multiply(){
    aux[1][1] = (mat[1][1]*prod[1][1] + mat[1][2]*prod[2][1])%mod;
    aux[1][2] = (mat[1][1]*prod[1][2] + mat[1][2]*prod[2][2])%mod;
    aux[2][1] = (mat[2][1]*prod[1][1] + mat[2][2]*prod[2][1])%mod;
    aux[2][2] = (mat[2][1]*prod[1][2] + mat[2][2]*prod[2][2])%mod;
    prod[1][1] = aux[1][1];
    prod[1][2] = aux[1][2];
    prod[2][1] = aux[2][1];
    prod[2][2] = aux[2][2];
}

void set_mat(){
    prod[1][1] = 1;
    prod[1][2] = 0;
    prod[2][1] = 0;
    prod[2][2] = 1;
    mat[1][1] = 0;
    mat[1][2] = 1;
    mat[2][1] = 1;
    mat[2][2] = 1;
}

void powlog(int k){
    set_mat();
    while(k!=0){
        if(k%2){
            prod_multiply();
        }
        self_multiply();
        k/=2;
    }
    fout<<prod[2][2]<<'\n';
}

int main() {
    int n;
    fin>>n;
    if(n == 0){
        fout<<'0'<<'\n';
    }else{
        powlog(n-1);
    }
    return 0;
}