#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MOD 666013

using namespace std;

long long ap[2][2]={ {1,1} , {1,0}  };
long long tn[2][2]={ {0,1 },{1,0}};

int main(){
    int n;
    int f1,f2,f3,f4;

    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    scanf("%d",&n);

    if(n==1 && n==2){
        printf("1");
        return 0;
    }


    while(n>0){
        if(n%2==1){
            f1=(  ( tn[0][0]*ap[0][0] )%MOD +(tn[0][1]*ap[1][0])%MOD ) % MOD;
            f2=(  ( tn[0][0]*ap[0][1] )%MOD +(tn[0][1]*ap[1][1])%MOD ) % MOD;
            tn[0][0]=f1;
            tn[0][1]=f2;

            f1=(  ( tn[1][0]*ap[0][0] )%MOD +(tn[1][1]*ap[1][0])%MOD ) % MOD;
            f2=(  ( tn[1][0]*ap[0][1] )%MOD +(tn[1][1]*ap[1][1])%MOD ) % MOD;
            tn[1][0]=f1;
            tn[1][1]=f2;
        }
        n/=2;

        if(n>0){
            f1=( (ap[0][0]*ap[0][0])%MOD + (ap[0][1] * ap[1][0])%MOD ) %MOD;
            f2=( (ap[0][0]*ap[0][1])%MOD + (ap[0][1] * ap[1][1])%MOD ) %MOD;
            f3=( (ap[1][0]*ap[0][0])%MOD + (ap[1][1] * ap[1][0])%MOD ) %MOD;
            f4=( (ap[1][0]*ap[0][1])%MOD + (ap[1][1] * ap[1][1])%MOD ) %MOD;
            ap[0][0]=f1;
            ap[0][1]=f2;
            ap[1][0]=f3;
            ap[1][1]=f4;
        }
    }

    printf("%lld\n",tn[0][0]);

    return 0;
}