#include <iostream>
#include <fstream>

using namespace std;

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

const int P = 666013;
struct matrix
{
    long long a11, a12, a22;
};
int K;

void prod(matrix &A, matrix &B)
{
    long long x = A.a11 * B.a11 + A.a12 * B.a12;
    long long y = A.a11 * B.a12 + A.a12 * B.a22;
    long long z = A.a12 * B.a12 + A.a22 * B.a22;
    A.a11 = x % P;
    A.a12 = y % P;
    A.a22 = z % P;
}

int putere(int n)
{
    matrix A = {1, 1, 0}, P = {1, 0, 1};
    while(n)
        if(n % 2 == 0)
        {
            prod(A, A);
            n /= 2;
        }
        else
        {
            prod(P, A);
            n--;
        }
    return P.a11;
}

int main()
{
    f >> K;
    if(K == 0)
        g << 0;
    else
        g << putere(K-1);
    f.close();
    g.close();
    return 0;
}