#include <fstream>

using namespace std;

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

int k;
long long a[2][2] = {{0, 1},{1, 1}};

void inmultire(long long t1[][2], long long t2[][2], long long rez[][2]){
    for(int i = 0;i<2;i++)
        for(int j = 0;j<2;j++){
            rez[i][j] = 0;
            for(int h = 0;h<2;h++)
                rez[i][j] += t1[i][h]*t2[h][j]%666013;
        }
}

void copiere(long long x[][2], long long y[][2]){
    for(int i = 0;i<2;i++)
        for(int j = 0;j<2;j++)
            x[i][j] = y[i][j];
}

void ridicare(long long b[][2], int putere){
    long long aux[2][2], aux2[2][2], c[2][2];
    if(putere == 1)
        return;
    copiere(aux, b);
    copiere(aux2, b);
    ridicare(aux, putere/2);
    inmultire(aux, aux, b);
    if(putere%2 == 1){
        inmultire(b, aux2, c);
        copiere(b, c);
    }
}

int main(){
    fin>>k;
    /// vreau sa obtin matricea {{f[n-1]}, {f[n]}}
    ridicare(a, k-1);
    fout<<a[1][1];
    return 0;
}