#include <iostream>
#include <fstream>

using namespace std;

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

const int mod = 666013;

void Produs(long long p[][2], long long a[][2], long long b[][2]) {
    p[0][0] = (a[0][0] * b[0][0] % mod + a[0][1] * b[1][0] % mod) % mod;
    p[0][1] = (a[0][0] * b[0][1] % mod + a[0][1] * b[1][1] % mod) % mod;
    p[1][0] = (a[1][0] * b[0][0] % mod + a[1][1] * b[1][0] % mod) % mod;
    p[1][1] = (a[1][0] * b[0][1] % mod + a[1][1] * b[1][1] % mod) % mod;
}

void Copie(long long a[][2], long long b[][2]) {
    for (int i = 0; i <= 1; i++)
        for (int j = 0; j <= 1; j++)
            a[i][j] = b[i][j];
}

int power(int n) {
    long long a[2][2] = { {1, 1}, {1, 0} };
    long long rez[2][2] = { {1, 0}, {0, 1} };
    long long aux[2][2];
    while (n) {
        if (n % 2 == 1) {
            Produs(aux, a, rez); // p = p * a
            Copie(rez, aux);
        }
        Produs(aux, a, a); // a = a * a
        Copie(a, aux);
        n /= 2;
    }
    return rez[0][1];
}

int main()
{
    int n;
    fin >> n;
    fout << power(n);
    return 0;
}