#include <fstream>
#define MOD 666013
using namespace std;
FILE * fin = fopen("kfib.in", "r");
FILE * fout = fopen("kfib.out", "w");

int k;
int z[5]={0, 0, 1, 1, 1};

void mputere(int[], int);
void produs(int[], int[], int[]);

int main()
{
    fscanf(fin, "%d", &k);
    mputere(z, k);
    fprintf(fout, "%d", z[3]);
    
    fclose(fin);
    fclose(fout);
    return 0;
}

void mputere(int z[], int k)
{
    if(k==1) return;
    
    int i, aux[5], sol[5];
    for (i=0; i<=4; i++) aux[i]=z[i];
    
    mputere(aux, k/2);
    produs(aux, aux, sol);
    
    if (k%2==1)
    {
        produs(sol, z, aux); // folosesc iar aux pentru rezultatul final
        for (i=0; i<=4; i++) z[i]=aux[i];
    }
    else
        for (i=0; i<=4; i++) z[i]=sol[i];
}

void produs(int a[], int b[], int sol[])
{
    sol[1]= ((long long int)a[1]*b[1] + (long long int)a[2]*b[3])%MOD;
    sol[2]= ((long long int)a[1]*b[2] + (long long int)a[2]*b[4])%MOD;
    sol[3]= ((long long int)a[3]*b[1] + (long long int)a[4]*b[3])%MOD;
    sol[4]= ((long long int)a[3]*b[2] + (long long int)a[4]*b[4])%MOD;
    
//    sol[1]= ((long long int)a[1]*b[1])%MOD + ((long long int)a[2]*b[3])%MOD;
//    sol[2]= ((long long int)a[1]*b[2])%MOD + ((long long int)a[2]*b[4])%MOD;
//    sol[3]= ((long long int)a[3]*b[1])%MOD + ((long long int)a[4]*b[3])%MOD;
//    sol[4]= ((long long int)a[3]*b[2])%MOD + ((long long int)a[4]*b[4])%MOD;
}