#include<cstdio>
#define MOD 666013
using namespace std;
struct matrice{
    long long int c1, c2, c3, c4;
} rez, x;
int k, i;
inline matrice inmulteste(matrice A, matrice B){
    matrice aux;
    aux.c1=((A.c1*B.c1)%MOD+(A.c2*B.c3)%MOD)%MOD;
    aux.c2=((A.c1*B.c2)%MOD+(A.c2*B.c4)%MOD)%MOD;
    aux.c3=((A.c3*B.c1)%MOD+(A.c4*B.c3)%MOD)%MOD;
    aux.c4=((A.c3*B.c2)%MOD+(A.c4*B.c4)%MOD)%MOD;
    return aux;
}
int main(){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d", &k);
    rez.c1=1; rez.c2=0; rez.c3=0; rez.c4=1; ///initial e I2
    x.c1=0; x.c2=1; x.c3=1; x.c4=1;
    for (i=0;(1<<i)<=k;i++){
        if ( ((1<<i)&k) > 0)
            rez=inmulteste(rez, x);
        x=inmulteste(x,x);
    }
    printf("%lld\n", rez.c3);
    ///printf("%lld %lld\n%lld %lld\n", rez.c1, rez.c2, rez.c3, rez.c4);
    return 0;
}