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

using namespace std;

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

int k, fibo[3][3], a[3][3];

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

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

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

void putere(int k)
{
    while (k)
    {
        if (k % 2 == 1)
            inmultire(fibo, a);
        inmultire(a, a);
        k /= 2;
    }
}


int main()
{
    f >> k;

    a[1][1] = 0;
    a[1][2] = 1;
    a[2][1] = 1;
    a[2][2] = 1;
    fibo[1][1] = 1;
    fibo[1][2] = 1;
    fibo[2][1] = 0;
    fibo[2][2] = 0;

    putere(k - 1);

    g << fibo[1][1];

    return 0;
}