#include <bits/stdc++.h>
#define int long long
#define MOD 666013
using namespace std;

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

int n, a;

int X[2][2]={0, 1,
             1, 1};

int A[2][2]={1, 1,
             0, 0};

int I[2][2]={1, 0,
             0, 1};

void mat_afis(int A[2][2]){
    for(int i=0; i<2; i++){
        for(int j=0; j<2; j++)
            cout<<A[i][j]<<" ";
        cout<<"\n";
    }
}

void mat_atr(int A[2][2], int B[2][2]){
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            A[i][j]=B[i][j];
}

void mat_mult(int A[2][2], int B[2][2]){
    int ANS[2][2];
    memset(ANS, 0, sizeof(ANS));
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++){
                ANS[i][j]+=((A[i][k]%MOD)*(B[k][j]%MOD))%MOD;
                ANS[i][j]%=MOD;
            }

    mat_atr(A, ANS);
}

void mat_power(int B[2][2], int exp){
    int ANS[2][2];
    mat_atr(ANS, I);
    while(exp){
        if(exp%2==1)
            mat_mult(ANS, B);
        mat_mult(B, B);
        exp/=2;
    }
    mat_atr(B, ANS);
}

int32_t main(){
    fin>>n;
    mat_power(X, n-1);
    mat_mult(A, X);
    fout<<A[0][0]%MOD;
}