#include <fstream>

using namespace std;


long long mod = 666013;

// functie pentru inmultirea matricelor
void multiplication(int A[2][2], int B[2][2]) {
    int C[2][2];

    for(int i = 0; i< 2; i ++) {

        for (int j = 0; j < 2; j++) {
            C[i][j] = 0;
        }
    }

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                C[i][j] = static_cast<int>(((C[i][j] + 1LL * A[i][k] * B[k][j]) % mod) );
            }
        }
    }
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            A[i][j] = C[i][j];
        }
    }

}



long long answer (long long a)
{
    int answer[2][2];
    answer[0][0] = answer[1][1] = 1;
    answer[0][1] = answer[1][0] = 0;

    int mult[2][2];
    mult[0][0] = 0;
    mult[0][1] = mult[1][0] = mult[1][1] = 1;

    while (a)
    {
        if ( a % 2 == 1)
        {
            multiplication(answer, mult);
        }
        multiplication(mult, mult);
        a /= 2;
    }

    return answer[1][0];
}


int main() {

    ifstream inputfile("kfib.in");
    ofstream outputfile("kfib.out");

    long long n;

    inputfile >> n;
    outputfile << answer(n);
    return 0;
}