#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#define MOD 666013
using namespace std;
int k,mat[3][3],sol[3][3];

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

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

void lgput(int p, int m[][3]){
    int c[3][3], aux[3][3], i;
    memcpy(c, mat, sizeof(mat));
    m[0][0] = m[1][1] = 1;
    for(int i = 0; (1<<i) <= p; i++){
        if(p&(1<<i)){
            memset(aux, 0, sizeof(aux));
            inmpMat(m, c, aux);
            memcpy(m, aux, sizeof(aux));
        }
        memset(aux, 0, sizeof(aux));
        inmpMat(c, c, aux);
        memcpy(c, aux, sizeof(c));
    }
}

int main()
{
    fin >> k;
    mat[0][0] = 0;
    mat[0][1] = mat[1][0] = mat[1][1] = 1;
    lgput(k-1, sol);
    fout << sol[1][1] << "\n";
    return 0;
}