#include <fstream>
#include <algorithm>
#define mod 666013

using namespace std;

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

long long k, fib[3][3], co[3][3];

void inmultire(long long a[3][3], long long b[3][3])
{
    long long c[3][3];

    c[0][0] = ((a[0][0] * b[0][0]) % mod + (a[0][1] * b[1][0]) % mod) % mod;
    c[0][1] = ((a[0][0] * b[0][1]) % mod + (a[0][1] * b[1][1]) % mod) % mod;
    c[1][0] = ((a[1][0] * b[0][0]) % mod + (a[1][1] * b[0][1]) % mod) % mod;
    c[1][1] = ((a[1][0] * b[0][1]) % mod + (a[1][1] * b[1][1]) % mod) % mod;

    for (int i = 0; i <= 1; ++ i)
        for (int j = 0; j <= 1; ++ j)
            a[i][j] = c[i][j];
}

int main()
{
    f >> k;

    co[0][0] = 0;
    co[0][1] = co[1][0] = co[1][1] = 1;
    fib[0][0] = fib[0][1] = 1;

    k --;

    while (k)
    {
        if (k % 2 == 1)
        {
            inmultire(fib, co);
            k --;
        }

        inmultire(co, co);
        k /= 2;
    }

    g << fib[0][0] << '\n';
    return 0;
}