#include <bits/stdc++.h>
using namespace std;
const int MOD = 666013;

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

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

void Cpy (int A[2][2], int B[2][2]) {
    A[0][0] = B[0][0];
    A[0][1] = B[0][1];
    A[1][0] = B[1][0];
    A[1][1] = B[1][1];
}

int Fib(int p) {
    int A[2][2] = {{1,1}, {1,0}}, B[2][2], C[2][2] = {{1,0}, {0,1}};
    while (p > 0) {
        if (p % 2 != 0)
        {
            Produs(C, A, B);
            Cpy(C, B);
        }
        Produs(A, A, B);
        Cpy(A, B);
        p /= 2;
    }
    return C[0][1];
}

int main()
{
    int n;
    f >> n;
    g << Fib(n);
    return 0;
}