#include <iostream>
#include <fstream>

using namespace std;

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

const int MOD = 666013;
int k;

void mult_mat(int a[2][2], int b[2][2], int rez[2][2]){
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            rez[i][j] = 0;
            for(int k = 0; k < 2; k++){
                rez[i][j] = (1LL * a[i][k] * b[k][j] % MOD + rez[i][j]) % MOD;
            }
        }
    }
}

void copy_mat(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];
        }
    }
}


int lg_put(){
    int p = k - 2;
    int rez[2][2] = {{1, 1}, {1, 0}};
    int a[2][2] = {{1, 1}, {1, 0}};
    int temp[2][2];

    while(p){
        if(p & 1){
            mult_mat(rez, a, temp);
            copy_mat(rez, temp);
        }
        mult_mat(a, a, temp);
        copy_mat(a, temp);
        p = (p >> 1);
    }

    return rez[0][0];
}

int main()
{
    fin >> k;
    if(k <= 1){
        fout << k;
    }else{
        fout << lg_put();
    }

    return 0;
}