#include <fstream>
#define MOD  666013

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

long long n,i,j,a[3][3],v[3][3],c[3][3];

void inmultire(long long v[3][3], long long a[3][3]){
    int d[3][3];
    d[1][1]=(v[1][1]*a[1][1]+v[1][2]*a[2][1])%MOD;
    d[1][2]=(v[1][1]*a[1][2]+v[1][2]*a[2][2])%MOD;
    d[2][1]=(v[2][1]*a[1][1]+v[2][2]*a[2][1])%MOD;
    d[2][2]=(v[2][1]*a[1][2]+v[2][2]*a[2][2])%MOD;
    v[1][1]=d[1][1];
    v[1][2]=d[1][2];
    v[2][1]=d[2][1];
    v[2][2]=d[2][2];
}

void rp(int k){
    while(k!=0){
       if(k%2==1)
          inmultire(c,a);
       inmultire(a,a);
       k/=2;
    }
}


int main()
{
    fin>>n;
    v[1][2]=1;
    a[1][2]=a[2][1]=a[2][2]=1;
    c[1][1]=c[2][2]=1;
    rp(n-1);
    inmultire(v,c);
    fout<<v[1][2];
    return 0;
}