#include <fstream>

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

long long t,x,y,z,a,b,c,f[4][4],mat[4][4];
long long n;
const int mod=666013;

void prod(long long a[4][4],long long b[4][4]){
    long long c[4][4];
    for(long long i=1;i<=3;i++){
        for(long long j=1;j<=3;j++){
            c[i][j]=0;
            for(long long k=1;k<=3;k++){
                c[i][j]+=((a[i][k]%mod)*(b[k][j]%mod))%mod;
                c[i][j]%=mod;
            }
        }
    }
    for(long long i=1;i<=3;i++){
        for(long long j=1;j<=3;j++){
            a[i][j]=c[i][j];
        }
    }
}
void pow(long long n){
    while(n!=0){
        if(n%2!=0){
            prod(mat,f);
        }
        prod(f,f);
        n/=2;
    }

}


int main()
{
        cin>>n;
        f[1][1]=1;
        f[2][1]=1;
        f[2][2]=0;
        f[1][2]=1;
        mat[1][1]=mat[2][2]=1;
        pow(n-1);
        if(n==0){
            cout<<0;
        }
        else
        cout<<mat[1][1]%mod<<'\n';
    return 0;
}