#include <fstream>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int MOD = 666013;
long long a[4][4], rez[4][4];

void inmulteste(long long a[4][4], long long b[4][4])
{
    long long aux[4][4];
    aux[1][1] = ((a[1][1]*b[1][1])%MOD + (a[1][2]*b[2][1])%MOD)%MOD;
    aux[1][2] = ((a[1][1]*b[1][2])%MOD + (a[1][2]*b[2][2])%MOD)%MOD;
    aux[2][1] = ((a[2][1]*b[1][1])%MOD + (a[2][2]*b[2][1])%MOD)%MOD;
    aux[2][2] = ((a[2][1]*b[1][2])%MOD + (a[2][2]*b[2][2])%MOD)%MOD;
    int i, j;
    for(i = 1; i <= 2; i++)
        for(j = 1; j <= 2; j++)
            a[i][j] = aux[i][j];


}

void putere(int p)
{
  if(p>=1){
    if(p %2 == 0)
    {

        inmulteste(a, a);
        putere(p/2);
    }
    else
    {
        inmulteste(rez, a);
        putere(p-1);
    }
  }
}

int main()
{
    int k;
    in >> k;
    a[1][1] = 0;
    a[1][2] = 1;
    a[2][2] = 1;
    a[2][1] = 1;
    rez[1][1]=rez[2][2]=1;
    putere(k-1);
    out << rez[2][2]%MOD;
    return 0;
}