#include <fstream>
#define MOD 666013
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
int k, n;
long long b[2][2];
void inmultire(long long a[2][2], long long b[2][2], long long c[2][2]){
    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            c[i][j]=0;
            for(int l=0;l<=1;l++){
                c[i][j]=(c[i][j]+a[i][l]*b[l][j])%MOD;
            }
        }
    }
}
void copiere(long long a[2][2], long long b[2][2]){
    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++)
            a[i][j]=b[i][j];
    }
}
int main() {
    cin>>k;
    if(k<=2){
        cout<<1;
        return 0;
    }
    long long p[2][2]={ {1,0},
                       {0,1}};
    long long a[2][2]={{1,1},
                       {1,0}};
    // a ^ (k-2) * {1
                //1}
    n=k-2;
    while(n){
        if(n%2){
            inmultire(p, a, b);
            copiere(p, b);
        }
        inmultire(a, a, b);
        copiere(a, b);
        n/=2;
    }
    cout<<(p[0][0]+p[0][1])%MOD;
    return 0;
}