#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;

int theMatrix[2][2] = {{0, 1}, {1, 1}};

void matrixMultiplication22(int original[][2], int other[][2]){
    int o[2][2] = {{other[0][0], other[0][1]}, {other[1][0], other[1][1]}};
    other[0][0] = other[0][1] = other[1][0] = other[1][1] = 0;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                other[i][j] += (1LL * original[i][k] * o[k][j]) % MOD;
            }
        }
    }
}

void matrixMultiplication12(int original[][2], int other[][2]){
    int o[1][2] = {{other[0][0], other[0][1]}};
    other[0][0] = ((1LL * original[0][0] * o[0][0]) % MOD + (1LL * original[1][0] * o[0][1]) % MOD) % MOD;
    other[0][1] = ((1LL * original[0][1] * o[0][0]) % MOD + (1LL * original[1][1] * o[0][1]) % MOD) % MOD;
}

void matrixPower(int original[][2], int pow, int mat[][2]){
    for(int i=0; (1<<i)<=pow; i++){
        if(((1<<i)&pow)>0)
            matrixMultiplication22(original, mat);
        int orig[2][2] = {{original[0][0], original[0][1]}, {original[1][0], original[1][1]}};
        matrixMultiplication22(orig, original);
    }
}

int main() {
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    int n;
    f>>n;
    int mat[2][2] = {{1, 0}, {0, 1}};
    matrixPower(theMatrix, n - 1, mat);
    int elem[1][2] = {{0, 1}};
    matrixMultiplication12(mat, elem);
    g<<elem[0][1];
    return 0;
}