#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;

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

struct matrice
{
    int mat[4][4];
    int n, m;
};

matrice multiply (matrice a, matrice b)
{
    matrice result;
    result.n = a.n;
    result.m = b.m;
    memset(result.mat, 0, sizeof(result.mat));
    for (int i = 1; i <= a.n; ++ i)
        for (int j = 1 ; j <= b.m; ++ j)
            for (int k = 1; k <= a.m; ++ k)
                result.mat[i][j] = (1LL * result.mat[i][j] + 1LL * a.mat[i][k] * b.mat[k][j]) % MOD;
    return result;
}

matrice lgput(matrice z, int b)
{
    if (b == 1)
        return z;
    if (b % 2)
        return multiply(z, lgput(multiply(z, z), b / 2));
    else
        return lgput(multiply(z,z), b / 2);
}

int main()
{
    matrice Z;
    Z.n = 2;
    Z.m = 2;
    Z.mat[1][1] = 0;
    Z.mat[1][2] = Z.mat[2][1] = Z.mat[2][2] = 1;

    matrice I;
    I.n = 1;
    I.m = 2;
    I.mat[1][1] = 0;
    I.mat[1][2] = 1;

    int k;
    f >> k;
    matrice nou = lgput(Z, k - 1);
    matrice ans = multiply(I, nou);
    g << ans.mat[1][2] << '\n';
}