#include <bits/stdc++.h>

std :: ifstream in ("kfib.in");

std :: ofstream out ("kfib.out");

const int mod = 666013;

int n;

int a[2][2];

int p[2][2];

int ans[2][2];

void multiply(int a[2][2], int b[2][2])
{
    int c[2][2];

    c[0][0] = c[0][1] = c[1][0] = c[1][1] = 0;

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

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

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

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

    for(int i = 0; i < 2; i ++)
    {
        for(int j = 0; j < 2; j ++)
        {
            a[i][j] = c[i][j];

            a[i][j] %= mod;
        }
    }
}

void pow(int n)
{
    while(n)
    {
        if(n % 2)
        {
            multiply(p, a);
        }

        multiply(a, a);

        n /= 2;
    }
}

int main()
{

    in >> n;

    a[0][0] = a[0][1] = a[1][0] = p[0][0] = p[1][1] = 1;

    pow(n - 2);

    ans[0][0] = ans[0][1] = 1;

    multiply(ans, p);

    out << ans[0][0];

    return 0;
}