#include <bits/stdc++.h>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
void inmultire(long long F[2][2], long long M[2][2])
{
    long long x =  F[0][0] * M[0][0] + F[0][1] * M[1][0];
    long long y =  F[0][0] * M[0][1] + F[0][1] * M[1][1];
    long long z =  F[1][0] * M[0][0] + F[1][1] * M[1][0];
    long long w =  F[1][0] * M[0][1] + F[1][1] * M[1][1];
    F[0][0] = x% 666013;
    F[0][1] = y% 666013;
    F[1][0] = z% 666013;
    F[1][1] = w% 666013;
}
void putere(long long F[2][2], long long n)
{
    if (n == 0 || n == 1)
        return;
    long long M[2][2] = {{1,1},{1,0}};
    putere(F, n / 2);
    inmultire(F, F);
    if (n % 2 != 0)
        inmultire(F, M);
}

long long kfib(long long n)
{
    long long F[2][2] = {{1,1},{1,0}};
    if (n == 0)
        return 0;
    putere(F, n - 1);
    return F[0][0];
}
int main()
{
    long long n;
        in >> n;
        out << kfib(n);
    return 0;
}