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

int main()
{
    int A[2][2], A_Temp[2][2], Sol[2][2], Temp[2][2], n;

    fin >> n;

    if(n == 0) fout << 0 << '\n';
    if(n == 1 || n == 2) fout << 1 << '\n';

    A[0][0] = 0, A[0][1] = 1, A[1][0] = 1, A[1][1] = 1;
    Sol[0][0] = 1, Sol[1][1] = 1, Sol[0][1] = 0, Sol[1][0] = 0;
    n--;

    while(n) {
        if(n & 1) {
            Temp[0][0] = ((1LL * Sol[0][0] * A[0][0]) % MOD + (1LL * Sol[0][1] * A[1][0]) % MOD ) % MOD;
            Temp[0][1] = ((1LL * Sol[0][0] * A[0][1]) % MOD + (1LL * Sol[0][1] * A[1][1]) % MOD ) % MOD;
            Temp[1][0] = ((1LL * Sol[1][0] * A[0][0]) % MOD + (1LL * Sol[1][1] * A[1][0]) % MOD ) % MOD;
            Temp[1][1] = ((1LL * Sol[1][0] * A[0][1]) % MOD + (1LL * Sol[1][1] * A[1][1]) % MOD ) % MOD;

            Sol[0][0] = Temp[0][0];
            Sol[0][1] = Temp[0][1];
            Sol[1][0] = Temp[1][0];
            Sol[1][1] = Temp[1][1];
        }

        A_Temp[0][0] = ((1LL * A[0][0] * A[0][0]) % MOD + (1LL * A[0][1] * A[1][0]) % MOD ) % MOD;
        A_Temp[0][1] = ((1LL * A[0][0] * A[0][1]) % MOD + (1LL * A[0][1] * A[1][1]) % MOD ) % MOD;
        A_Temp[1][0] = ((1LL * A[1][0] * A[0][0]) % MOD + (1LL * A[1][1] * A[1][0]) % MOD ) % MOD;
        A_Temp[1][1] = ((1LL * A[1][0] * A[0][1]) % MOD + (1LL * A[1][1] * A[1][1]) % MOD ) % MOD;

        A[0][0] = A_Temp[0][0];
        A[0][1] = A_Temp[0][1];
        A[1][0] = A_Temp[1][0];
        A[1][1] = A_Temp[1][1];

        n >>= 1;
    }

    fout << Sol[1][1] << '\n';
    return 0;
}