#include <fstream>
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

const int mod = 666013;
int k;

long long a[2][2] = {{1, 1}, {1, 0}}, b[2][2] = {{1, 0}, {0, 1}}, rez[2][2];

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

void copy_matrix(long long a[][2], long long b[][2]) {
    a[0][0] = b[0][0];
    a[0][1] = b[0][1];
    a[1][0] = b[1][0];
    a[1][1] = b[1][1];
}

long long fib(int k) {

    while(k) {
        if(k & 1) {
            multiply_matrix(rez, a, b);
            copy_matrix(b, rez);
        }
        multiply_matrix(rez, a, a);
        copy_matrix(a, rez);
        k /= 2;
    }
    return b[0][1];
}

int main()
{
    f >> k;
    g << fib(k);
}