#include <bits/stdc++.h>

using namespace std;
int Mod=666013;
int A[3][3],C[3][3];

void solve(int n){
    if(n==1){
        C[1][1]=0, C[1][2]=1;
        C[2][1]=1, C[2][2]=1;
        return;
    }
    solve(n/2);
    A[1][1]=(1ll*C[1][1]*C[1][1]+1ll*C[1][2]*C[2][1])%Mod;
    A[1][2]=(1ll*C[1][1]*C[1][2]+1ll*C[1][2]*C[2][2])%Mod;
    A[2][1]=(1ll*C[1][1]*C[2][1]+1ll*C[2][1]*C[2][2])%Mod;
    A[2][2]=(1ll*C[1][2]*C[2][1]+1ll*C[2][2]*C[2][2])%Mod;

    if(n%2){
        C[1][1]=A[1][2];
        C[1][2]=(A[1][1]+A[1][2])%Mod;
        C[2][1]=A[2][2];
        C[2][2]=(A[2][1]+A[2][2])%Mod;
    }
    else{
        C[1][1]=A[1][1];
        C[1][2]=A[1][2];
        C[2][1]=A[2][1];
        C[2][2]=A[2][2];
    }
}

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

    int n;
    scanf("%d",&n);
    if(n==0){
        printf("0\n");
        return 0;
    }
    if(n==1 or n==2){
        printf("1\n");
        return 0;
    }
    solve(n-1);
    printf("%d\n",C[2][2]);


    return 0;
}