#include <fstream>

#define MOD 666013

using namespace std;

long long A[2][2];
long long B[2][2];

void inmultire(/*long long A[][], long long B[][]*/)
{
    long long a, b, c, d;
    a = A[0][0];
    b = A[0][1];
    c = A[1][0];
    d = A[1][1];

    A[0][0] = (a * B[0][0] + b * B[1][0]) % MOD;
    A[0][1] = (a * B[0][1] + b * B[1][1]) % MOD;
    A[1][0] = (c * B[0][0] + d * B[1][0]) % MOD;
    A[1][1] = (c * B[0][1] + d * B[1][1]) % MOD;
}
void patrat(/*long long A[][]*/)
{
    long long a, b, c, d;
    a = B[0][0];
    b = B[0][1];
    c = B[1][0];
    d = B[1][1];

    B[0][0] = (a * a + b * c) % MOD;
    B[0][1] = (a * c + b * d) % MOD;
    B[1][0] = (c * a + b * d) % MOD;
    B[1][1] = (c * b + d * d) % MOD;
}

int main()
{
    FILE * fin = fopen ("kfib.in", "r");
    FILE * fout = fopen ("kfib.out", "w");

    long long n;
    fscanf(fin, "%lld", &n);

    --n;
    B[1][1] = B[1][0] = B[0][1] = A[0][0] = A[1][1] = 1;
    for (int i = 1; i <= n; i <<= 1)
    {
        if (i & n)
        {
            inmultire(/*M2, M1*/);
        }
        patrat(/*M1*/);
    }
    if (n >= 0)
    {
        fprintf(fout, "%lld\n", (A[0][0]+A[1][0]) % MOD);
    }
    else {
        fprintf(fout, "0\n");
    }

    fclose(fin);
    fclose(fout);
    return 0;
}