#include <iostream>
#include <stdio.h>
using namespace std;

class Matrita {
    public:
    long long elem[2][2];

    Matrita(const int _A1, const int _A2, const int _B1, const int _B2) {
        elem[0][0] = _A1;
        elem[0][1] = _A2;
        elem[1][0] = _B1;
        elem[1][1] = _B2;
    }

    Matrita() {
        elem[0][0] = 0;
        elem[0][1] = 0;
        elem[1][0] = 0;
        elem[1][1] = 0;
    }

    Matrita operator*(const Matrita _cobai) {
        return Matrita(
            ((elem[0][0] * _cobai.elem[0][0]) + (elem[0][1] * _cobai.elem[1][0])) % 666013,
            ((elem[0][0] * _cobai.elem[1][0]) + (elem[0][1] * _cobai.elem[1][1])) % 666013,
            ((elem[1][0] * _cobai.elem[0][0]) + (elem[1][1] * _cobai.elem[1][0])) % 666013,
            ((elem[1][0] * _cobai.elem[1][0]) + (elem[1][1] * _cobai.elem[1][1])) % 666013);
    }

    void Afis() {
        cout << elem[0][0] << " " << elem[0][1] << '\n';
        cout << elem[1][0] << " " << elem[1][1] << '\n';
    }
};

Matrita pov(Matrita _cobai, int _p) {
    if (_p == 0) return Matrita (1, 1, 1, 1);
    if (_p == 1) return _cobai;
    if (_p % 2) return _cobai * pov(_cobai, _p - 1);
    else return pov(_cobai, _p/2) * pov(_cobai, _p/2);
}

int main() {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int x;
    cin >> x;
    cout << (pov(Matrita(0,1,1,1), x).elem[0][1]) % 666013;
}