#include <fstream>
#include <cstdio>
#include <cstring>

using namespace std;

#define mod 666013

int n,i;
int m[3][3];
 int S[3][3];


inline void rpl (int a[][3],int b[][3],int c[][3]){

    for(int i=0;i<2;++i)
    for(int j=0;j<2;++j)
    for(int k=0;k<2;++k)
    c[i][j]=(c[i][j]+ 1LL*a[i][k]*b[k][j] )%mod;

}

void solve (int x,int a[][3]){

    int b[3][3];
    a[0][0]=a[1][1]=1;
    for(int i=0;(1<<i)<=x;++i){
        if(x & (1<<i)){
            memset(b,0,sizeof(b));
            rpl(a,m,b);
            memcpy(a,b,sizeof(b));
        }
        memset(b,0,sizeof(b));
        rpl(m,m,b);
        memcpy(m,b,sizeof(m));
    }

}

int main ()
{

    ifstream in ("kfib.in");
    in>>n;
    in.close ();
    m[1][1]=m[1][0]=m[0][1]=1;
    solve (n-1,S);
    freopen ("kfib.out","w",stdout);
    printf("%d\n",S[1][1]);

return 0;}