#include <fstream>
#include <iostream>

using namespace std;

const int mod = 666013;

void mult(int a[2][2], int b[2][2])
{
    int res[2][2];
    res[0][0] = ((1LL * a[0][0] * b[0][0]) + (1LL * a[0][1] * b[1][0])) % mod;
    res[0][1] = ((1LL * a[0][0] * b[0][1]) + (1LL * a[0][1] * b[1][1])) % mod;
    res[1][0] = ((1LL * a[1][0] * b[0][0]) + (1LL * a[1][1] * b[1][0])) % mod;
    res[1][1] = ((1LL * a[1][0] * b[0][1]) + (1LL * a[1][1] * b[1][1])) % mod;
    a[0][0] = res[0][0];
    a[1][0] = res[1][0];
    a[0][1] = res[0][1];
    a[1][1] = res[1][1];
}

void logpow(int a[2][2], int b)
{
    int p[2][2];
    p[0][0] = p[1][1] = 1;
    p[0][1] = p[1][0] = 0;

    while (b)
    {
        if (b % 2 == 1)
            mult(p, a);
        mult(a, a);
        b /= 2;
    }
    a[0][0] = p[0][0];
    a[1][0] = p[1][0];
    a[0][1] = p[0][1];
    a[1][1] = p[1][1];
}

int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");

    int k;
    in >> k;

    int m[2][2];
    m[0][0] = 0;
    m[0][1] = 1;
    m[1][0] = 1;
    m[1][1] = 1;

    logpow(m, k-1);

    out << m[1][1] << '\n';


    return 0;
}