#include <stdio.h>
using namespace std;

#define MOD 666013

typedef unsigned long long Ull;

const Ull M[2][2] = {0, 1, 1, 1};

void put_mat(Ull X[2][2], unsigned k)
{
    if(k > 1)
    {
        put_mat(X, k/2);
    
        static Ull aux[2][2];
        
        aux[0][0] = ((X[0][0]*X[0][0])%MOD + (X[0][1]*X[1][0])%MOD) % MOD;
        aux[0][1] = ((X[0][0]*X[0][1])%MOD + (X[0][1]*X[1][1])%MOD) % MOD;
        aux[1][0] = ((X[1][0]*X[0][0])%MOD + (X[1][1]*X[1][0])%MOD) % MOD;
        aux[1][1] = ((X[1][0]*X[0][1])%MOD + (X[1][1]*X[1][1])%MOD) % MOD;
        
        if(k%2 != 0)
        {
            X[0][0] = ((aux[0][0]*M[0][0])%MOD + (aux[0][1]*M[1][0])%MOD) % MOD;
            X[0][1] = ((aux[0][0]*M[0][1])%MOD + (aux[0][1]*M[1][1])%MOD) % MOD;
            X[1][0] = ((aux[1][0]*M[0][0])%MOD + (aux[1][1]*M[1][0])%MOD) % MOD;
            X[1][1] = ((aux[1][0]*M[0][1])%MOD + (aux[1][1]*M[1][1])%MOD) % MOD;
        }
        else
        {
            X[0][0] = aux[0][0];
            X[0][1] = aux[0][1];
            X[1][0] = aux[1][0];
            X[1][1] = aux[1][1];
        }
    }
}

Ull fibo(unsigned k)
{
    if(k <= 1)
        return k;

    Ull X[2][2] = {0,1,1,1};
    
    put_mat(X, k);
    
    return X[1][0];
}

int main()
{
    unsigned k;

    FILE* fin = fopen("kfib.in", "r");
    FILE* fout = fopen("kfib.out", "w");
    
    fscanf(fin, "%u", &k);
    fprintf(fout, "%llu", fibo(k));
    
    fclose(fin);
    fclose(fout);
    
    return 0;
}