#include <bits/stdc++.h>
#define MOD 666013
using namespace std;

ifstream ci("kfib.in");
ofstream cou("kfib.out");

long long n;
//mi = m1 * z^i-1
long long v[3][3];//sol fin
long long sol[3][3];//sol la fct aia
long long p[3][3];

void ridicamatrice(long long a[3][3],long long b[3][3]){

    sol[1][1]=a[1][1]*b[1][1]+a[1][2]*b[2][1];
    sol[1][2]=a[1][1]*b[1][2]+a[1][2]*b[2][2];
    sol[2][1]=a[2][1]*b[1][1]+a[2][2]*b[1][2];
    sol[2][2]=a[1][2]*b[2][1]+a[2][2]*b[2][2];

}


void ridlaput(long long put){
    //calc z^i-1
    //p = solutia
    //v = x
    while(put){
        if(put%2==1){
            ridicamatrice(p,v);
            p[1][1]=1LL*sol[1][1]%MOD;
            p[2][1]=1LL*sol[2][1]%MOD;
            p[1][2]=1LL*sol[1][2]%MOD;
            p[2][2]=1LL*sol[2][2]%MOD;
        }
        put=put/2;
        ridicamatrice(v,v);
        //sol e v^2;
        v[1][1]=1LL*sol[1][1]%MOD;
        v[2][1]=1LL*sol[2][1]%MOD;
        v[1][2]=1LL*sol[1][2]%MOD;
        v[2][2]=1LL*sol[2][2]%MOD;

    }
}

int main()
{
    ci>>n;
    long long rez;
    v[1][1]=0;
    v[1][2]=1;
    v[2][1]=1;
    v[2][2]=1;

    p[1][1]=0;
    p[1][2]=1;
    p[2][1]=1;
    p[2][2]=1;

    ci>>n;
    ridlaput(n-3);

    //mi = m1 * z^i-1
    //m1=(1,1)

    rez=(p[1][2]*1+p[2][2]*1)%MOD;
    cou<<rez;

    return 0;
}