#include <fstream>
#define mod 666013

using namespace std;

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

long long k, a[3][3], mat[3][3];

void inmultire(long long a[3][3], long long b[3][3])
{
    int 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;
    a[0][0] = 1;
    a[0][1] = 1;
    mat[0][0] = 0;
    mat[0][1] = mat[1][0] = mat[1][1] = 1;

    k --;

    while (k)
    {
        if (k % 2 == 1)
        {
            k --;
            inmultire(a, mat);
        }
        inmultire(mat, mat);
        k /= 2;
    }

   // inmultire(a, mat);

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