#include <fstream>
#include <cstring>
#define MOD 666013
using namespace std;

int K;
int mat[50][5];
int A[5];
int B[5] = {0, 1, 0, 0, 1};

void matrix_mul (int A[], int B[], int C[])
{
    C[1] = (1LL * A[1] * B[1] + 1LL * A[2] * B[3]) % MOD;
    C[2] = (1LL * A[1] * B[2] + 1LL * A[2] * B[4]) % MOD;
    C[3] = (1LL * A[3] * B[1] + 1LL * A[4] * B[3]) % MOD;
    C[4] = (1LL * A[3] * B[2] + 1LL * A[4] * B[4]) % MOD;
}

int main ()
{
    ifstream fin ("kfib.in");
    ofstream fout ("kfib.out");
    fin >> K;
    if (K == 0)
    {
        fout << 0;
        fout.close ();
        return 0;
    }
    fin.close ();
    mat[0][1] = 0;
    mat[0][2] = 1;
    mat[0][3] = 1;
    mat[0][4] = 1;
    for (int i = 1; i <= 31; i++)
        matrix_mul (mat[i - 1], mat[i - 1], mat[i]);
    K--;
    for (int i = 31; i >= 0; i--)
    {
        if ((1LL << i) <= 1LL * K)
        {
            K -= (1 << i);
            matrix_mul (B, mat[i], A);
            memcpy (B, A, sizeof (A));
        }
    }
    fout << B[4];
    fout.close ();
    return 0;
}