#include <stdio.h>
#define fr(i,a,b) for(int i=a;i<b;++i)
#define MOD 666013
#define ll long long
ll a[2][2]={{0,1},{1,1}};
ll an[2][2];
void prod(ll (*a)[2],ll (*b)[2]){ //a=a*b
    ll t[2][2],tb[2][2];
    fr(i,0,2)fr(j,0,2)t[i][j]=a[i][j],tb[i][j]=b[i][j];

    fr(r,0,2){
        fr(c,0,2){
            a[r][c]=0;
            fr(i,0,2)a[r][c]+=t[r][i]*tb[i][c],
            a[r][c]%=MOD;
            }
        }

    }
void exp(int n){
    if(n==-1){
        fr(i,0,2)fr(j,0,2) an[i][j]=0;
        return;
        }
    if(n==0){
        an[0][0]=an[1][1]=1;
        an[1][0]=an[0][1]=0;
        return;
        }
    if(n==1){
        fr(i,0,2)fr(j,0,2)an[i][j]=a[i][j];
        return;
        }
    exp(n/2);
    prod(an,an);
    if(n%2) prod(an,a);
    }
int main(){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int n;
    scanf("%i",&n);
    a[0][0]=0;
    a[1][0]=a[1][1]=a[0][1]=1;
    exp(n-1);
    int f0=0,f1=1;
    printf("%lli\n",an[1][1]);
    return 0;
    }