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

class MX {
    public:
    long long val[2][2];
};

MX multiply(MX cobai, MX multiplier) {
    MX res;
    res.val[0][0] = (cobai.val[0][0] * multiplier.val[0][0] + cobai.val[0][1] * multiplier.val[1][0]) % 666013;
    res.val[0][1] = (cobai.val[0][0] * multiplier.val[0][1] + cobai.val[0][1] * multiplier.val[1][1]) % 666013;
    res.val[1][0] = (cobai.val[1][0] * multiplier.val[0][0] + cobai.val[1][1] * multiplier.val[1][0]) % 666013;
    res.val[1][1] = (cobai.val[1][0] * multiplier.val[0][1] + cobai.val[1][1] * multiplier.val[1][1]) % 666013;

    return res;
}

MX pw(MX cobai, int put) {
    if (put == 1) return cobai;
    if (put % 2) return multiply(cobai, pw(cobai, put - 1));
    else return multiply(pw(cobai, put/2), pw(cobai, put/2));
}

int main() { //metoda "optimizata" yupi
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    MX cobai;
    cobai.val[0][0] = 0;
    cobai.val[0][1] = 1;
    cobai.val[1][1] = 1;
    cobai.val[1][0] = 1;
    int x;
    cin >> x;
    cout << pw(cobai, x).val[0][1];
}