#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long a[3][3]={
    {0,0,0},
    {0,1,1},
    {0,1,0},
};
long long c[3][3],m=666013,n;
void produs(long long a[3][3],long long b[3][3]){
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            c[i][j]=0;
            for(int k=1;k<=2;k++){
                c[i][j]+=a[i][k]*b[k][j]%m;
                c[i][j]%=m;
            }
        }
    }
}
long long putere(long long b){
    long long r[3][3]={
        {0,0,0},
        {0,1,0},
        {0,0,1},
    };

    while(b!=0){
        if(b%2==1){
            produs(r,a);
            memcpy(r,c,sizeof(c));
        }
        memset(c,0,sizeof(c));
        produs(a,a);
        memcpy(a,c,sizeof(c));

        b/=2;
    }
    return r[1][1]%m+r[1][2]%m;
}
int main(){
    fin>>n;
    if(n==1 || n==2){
        fout<<1;
        return 0;
    }
    fout<<putere(n-2)%m;
    return 0;
}