#include <iostream>
#include <bits/stdc++.h>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

long long int a[2][2],b[2][2],ans[2][2],n;
const int mod=666013;

void init(){
ans[0][0]=1;
ans[0][1]=1;
a[1][0]=1;
a[0][1]=1;
a[1][1]=1;
}

void multi(long long int a[2][2],long long int b[2][2]){
    int c[2][2]={};
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                c[i][j]=(c[i][j]+(1LL*a[i][k]*b[k][j])%mod)%mod;
            }
        }
    }
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            a[i][j]=c[i][j];
        }
    }
}

void exporap(long long int pow){
    while(pow>0){
        if(pow%2){
            multi(ans,a);
        }
        multi(a,a);
        pow=pow/2;
    }

}




int main()
{
    fin>>n;
    init();
    exporap(n-1);
    fout<<ans[0][0];
}