#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int MOD = 666013;

int K,F[1][2],M[2][2];

void Multiply(int A[2][2], int B[2][2])
{
    long long C[2][2] = {0};
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            {
                for(int k = 0; k < 2; ++k)
                {
                    C[i][j] += 1LL * A[i][k] * B[k][j];
                }
                 C[i][j] %= MOD;

            }
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            A[i][j] = C[i][j];
}
void Multiply2(int A[1][2], int B[2][2])
{
    long long C[1][2] = {0};
    for(int i = 0; i < 1; ++i)
        for(int j = 0; j < 2; ++j)
            {
                for(int k = 0; k < 2; ++k)
                {
                    C[i][j] += 1LL * A[i][k] * B[k][j];
                }
                 C[i][j] %= MOD;

            }
    for(int i = 0; i < 1; ++i)
        for(int j = 0; j < 2; ++j)
            A[i][j] = C[i][j];
}
int main()
{
    fin >> K;

    F[0][1] = 1;
    M[0][1] = M[1][0] = M[1][1] = 1;

    while(K)
    {
        if(K % 2 == 1)
            Multiply2(F,M);
        Multiply(M,M);
        K = K /2;
    }

    fout << F[0][0] <<"\n";
    return 0;
}