#include <fstream>

using namespace std;

ifstream cin ("kfib.in");
ofstream cout ("kfib.out");

const int MOD = 666013;
const int N = 4;

int n;
int f[N][N];

void produs (int c[N][N], int a[N][N],int b[N][N])
{
    int n = 2, m = 2, p = 2, aux[N][N];
    for (int i = 1; i <= m; ++i)
        for (int k = 1; k <= p; ++k)
        {
            aux[i][k] = 0;
            for (int j = 1; j <= n; ++j)
            {
                aux[i][k] += (1LL * a[i][j] * b[j][k]) % MOD;
                aux[i][k] %= MOD;
            }
        }
    for (int i = 1; i <= m; ++i)
        for (int k = 1; k <= p; ++k)
            c[i][k] = aux[i][k] % MOD;
}

int po (int n)
{
    int u[N][N];
    u[1][1] = u[2][2] = 1;
    u[1][2] = u[2][1] = 0;
    while (n)
    {
        if (n & 1)
            produs(u, u, f);
        produs (f, f, f);
        n >>= 1;
    }
    return u[1][1];
}
int main()
{
    cin >> n;
    f[1][1] = f[1][2] = f[2][1] = 1;
    cout << po(n - 1);
}