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

struct Matrix {
    int m[2][2];

    Matrix(int a, int b, int c, int d) {
        m[0][0] = a;
        m[0][1] = b;
        m[1][0] = c;
        m[1][1] = d;
    }

    Matrix() {
       m[0][0] = m[0][1] = m[1][0] = m[1][1] = 0;
    }

    friend Matrix operator * (Matrix A, Matrix B) {
        return Matrix(  (1LL * A.m[0][0] * B.m[0][0] + 1LL * A.m[0][1] * B.m[1][0]) % MOD,
                        (1LL * A.m[0][0] * B.m[0][1] + 1LL * A.m[0][1] * B.m[1][1]) % MOD,
                        (1LL * A.m[1][0] * B.m[0][0] + 1LL * A.m[1][1] * B.m[1][0]) % MOD,
                        (1LL * A.m[1][0] * B.m[0][1] + 1LL * A.m[1][1] * B.m[1][1]) % MOD);
    }
};

int main() {
    int n, i, p2;
    std::ifstream fin("kfib.in");
    std::ofstream fout("kfib.out");
    fin >> n;
    p2 = (int)log2(--n);
    Matrix v[32], rez(1, 0, 0, 1);
    v[0] = Matrix(1, 1, 1, 0);
    for(i = 1; i <= p2; ++i)
        v[i] = v[i-1] * v[i-1];

    while(n) {
        rez = rez * v[p2];
        n -= (1 << p2);
        p2 = (int)log2(n);
    }
    fout << (rez.m[0][0]) % MOD;
}