#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

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

int k;
long long sol[3][3], aux[3][3];

void inmultireMatrice (long long a[3][3], long long b[3][3]){
    long long c[3][3];
    for (int i=1; i<=2; i++){
        for (int j=1; j<=2; j++){
            c[i][j] = 0;
            for (int p=1; p<=2; p++){
                c[i][j] = (c[i][j] + a[i][p]*b[p][j])%MOD;
            }
        }
    }
    for (int i=1; i<=2; i++){
        for (int j=1; j<=2; j++){
            a[i][j] = c[i][j];
        }
    }
}

int main(){
    fin >> k;
    if (k <= 2){
        fout << 1;
        return 0;
    }
    k -= 2;
    aux[1][1] = aux[1][2] = aux[2][1] = 1;
    sol[1][1] = sol[2][2] = 1;
    for (;k;k>>=1){
        if (k&1){
            inmultireMatrice(sol, aux);
        }
        inmultireMatrice(aux, aux);
    }
    fout << (sol[1][1] + sol[1][2])%MOD;
    return 0;
}