#include <fstream>

using namespace std;
const int MOD = 666013;

struct MAT
{
    long long a11, a12, a22;
};

MAT A = {1, 1, 0}, I = {1, 0, 1};

ifstream fin("kfib.in");
ofstream fout("kfib.out");

void mul(MAT &A, MAT &B)
{
    long long x = A.a11 * B.a11 + A.a12 * B.a12,
              y = A.a11 * B.a12 + A.a12 * B.a22,
              z = A.a12 * B.a12 + A.a22 * B.a22;
    A.a11 = x % MOD;
    A.a12 = y % MOD;
    A.a22 = z % MOD;
}

void exp(int p)
{
    while(p)
    {
        if(p & 1) mul(I, A);
        mul(A, A);
        p >>= 1;
    }
}

int main()
{
    int k;
    fin >> k;
    if(k > 0)
    {
        exp(k - 1);
        fout << I.a11;
    }
    else
        fout << '0';
    return 0;
}