#include <cstdio>
#define MOD 666013
long long f[3][3],r[3][3],a[3][3];

void pow(int n){
    if(n>1){
        pow(n/2);
        a[0][0]=(r[0][0]*r[0][0]+r[0][1]*r[1][0])%MOD;
        a[0][1]=(r[0][0]*r[0][1]+r[0][1]*r[1][1])%MOD;
        a[1][0]=(r[1][0]*r[0][0]+r[1][1]*r[1][0])%MOD;
        a[1][1]=(r[1][0]*r[0][1]+r[1][1]*r[1][1])%MOD;
        for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)r[i][j]=a[i][j];
        if(n%2==1){
        a[0][0]=(r[0][0]*f[0][0]+r[0][1]*f[1][0])%MOD;
        a[0][1]=(r[0][0]*f[0][1]+r[0][1]*f[1][1])%MOD;
        a[1][0]=(r[1][0]*f[0][0]+r[1][1]*f[1][0])%MOD;
        a[1][1]=(r[1][0]*f[0][1]+r[1][1]*f[1][1])%MOD;
        for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)r[i][j]=a[i][j]; }
    }
}

int main(){
    int n;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    f[0][1]=f[1][0]=f[1][1]=1;
    r[0][1]=r[1][0]=r[1][1]=1;
    pow(n-1);
    printf("%lld\n",r[1][1]);
}