#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;

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

void multiply(int a[2][2], int b[2][2], int result[2][2]) {
    int temp[2][2];
    temp[0][0] = (1LL * a[0][0] * b[0][0] + 1LL * a[0][1] * b[1][0]) % mod;
    temp[0][1] = (1LL * a[0][0] * b[0][1] + 1LL * a[0][1] * b[1][1]) % mod;
    temp[1][0] = (1LL * a[1][0] * b[0][0] + 1LL * a[1][1] * b[1][0]) % mod;
    temp[1][1] = (1LL * a[1][0] * b[0][1] + 1LL * a[1][1] * b[1][1]) % mod;

    result[0][0] = temp[0][0];
    result[0][1] = temp[0][1];
    result[1][0] = temp[1][0];
    result[1][1] = temp[1][1];
}

void power(int base[2][2], int exp, int result[2][2]) {
    while (exp) {
        if (exp & 1) {
            multiply(result, base, result);
        }
        multiply(base, base, base);
        exp >>= 1;
    }
}

int main() {
    int p;
    fin >> p;
    if (p == 0) {
        fout << 0 << endl;
        return 0;
    }
    int baza[2][2] = {{0, 1}, {1, 1}};
    int rezultat[2][2] = {{1, 0}, {0, 1}};
    power(baza, p - 1, rezultat);
    fout << rezultat[1][1] << endl;
    return 0;
}