#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int MOD = 666013;
const char inf[] = "kfib.in";
const char outf[] = "kfib.out";

struct matrice
{
    int a11,a12,a22,a21;
}fib,z;

int n;

FILE *in=fopen(inf,"r"),*out=fopen(outf,"w");


matrice inmult(matrice A, matrice B)
{
    matrice rez;
    rez.a11=((A.a11*B.a11)%MOD+(A.a12*B.a21)%MOD)%MOD;
    rez.a12=((A.a11*B.a12)%MOD+(A.a12*B.a22)%MOD)%MOD;
    rez.a21=((A.a21*B.a11)%MOD+(A.a22*B.a21)%MOD)%MOD;
    rez.a22=((A.a21*B.a12)%MOD+(A.a22*B.a22)%MOD)%MOD;
    return rez;
}

matrice pow(int k)
{
    if(k==1)
        return z;
    matrice aux=pow(k/2);
    matrice rez=inmult(aux, aux);
    if(k%2==1)
        rez=inmult(rez, z);
    return rez;
}


int main()
{
    fscanf(in,"%d",&n);
    z.a11=1; z.a12=1;
    z.a21=1; z.a22=0;
    fib=pow(n-1);
    fprintf(out,"%d",fib.a11);
    return 0;
}