#include <fstream>
using namespace std;
ifstream in ("kfib.in");
ofstream out ("kfib.out");
const int mod = 666013;
long long n, Z[2][2], S[2][2];

void inmultire(long long F1[2][2], long long F2[2][2], long long Sol[2][2])
{
    long long Rez[2][2]; Rez[0][0] = Rez[0][1] = Rez[1][0] = Rez[1][1] = 0;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                Rez[i][j] = (Rez[i][j] + 1LL * F1[i][k] * F2[k][j]) % mod;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            Sol[i][j] = Rez[i][j];
}

void lgput(long long Z[2][2], int n, long long Sol[2][2])
{
    if (n == 1) inmultire(Sol, Z, Sol);
    else
    {
        long long T[2][2]; T[0][0] = T[1][1] = 1; T[0][1] = T[1][0] = 0;
        lgput(Z, n/2, T);
        if (n & 1) { inmultire(T, T, Sol); inmultire(Sol, Z, Sol); }
        else inmultire (T, T, Sol);
    }
}

int main()
{
    in >> n;
    Z[0][0] = 0; Z[0][1] = Z[1][0] = Z[1][1] = 1;
    S[0][0] = S[1][1] = 1; S[0][1] = S[1][0] = 0;
    lgput(Z, n - 1, S);
    out << S[1][1] << '\n';
    out.close(); return 0;
}