#include <fstream>

using namespace std;

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

long long mod = 666013;

// functie pentru inmultirea matricelor
void multiplication(int A[][2], int B[][2]) {
    int C[2][2];
    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 2; j++) {
            for (int k = 1; 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;
}


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