#include<fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

int n;
const int mod = 666013;

void inmultire(long long x[2][2], long long y[2][2]){

    long long aux[2][2];
    long long i, j, s, l;
    for(i = 0; i <= 1; i++)
        for(j = 0; j <= 1; j++){

            s = 0;
            for(l = 0; l <= 1; l++)
                s += ((x[i][l] * y[l][j]))%mod;
            aux[i][j] = s%mod;
        }
    for(i = 0; i <= 1; i++)
    for(j = 0; j <= 1; j++)
        x[i][j] = aux[i][j];

}

void log_pow(long long a[2][2], long long n){

    long long aux[2][2];
   aux[0][1] = aux[1][1] = aux[1][0] = 1;
   aux[0][0] = 0;
    n--;
    while(n){

        if(n % 2)
            inmultire(aux, a);
        n >>= 1;
        inmultire(a, a);
    }

    g << aux[1][1];

}

int main(){

    long long a[2][2];
    a[0][0] = 0;
    a[0][1] = 1;
    a[1][1] = 1;
    a[1][0] = 1;
    f >> n;
    log_pow(a, n - 1);
}