#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

void inm_mat(int a[2][2], int b[2][2], int rsl[2][2]) {
    rsl[0][0] = (a[0][0] % 666013 * b[0][0] % 666013 + a[0][1]*b[1][0]) % 666013;
    rsl[0][1] = (a[0][0] % 666013 * b[0][1] % 666013 + a[0][1]*b[1][1]) % 666013;
    rsl[1][0] = (a[1][0] % 666013 * b[0][0] % 666013 + a[1][1]*b[1][0]) % 666013;
    rsl[1][1] = (a[1][0] % 666013 * b[0][1] % 666013 + a[1][1]*b[1][1]) % 666013;
}

void copiere(int ans[2][2], int temp[2][2]) {
    ans[0][0] = temp[0][0];
    ans[0][1] = temp[0][1];
    ans[1][0] = temp[1][0];
    ans[1][1] = temp[1][1];
}

void ridicare(int A[2][2], int n) {
    int ans[2][2] = {1, 0, 0, 1};
    int temp[2][2] = {1, 1, 1, 1};

    while (n) {
        if (n % 2 == 1){

            inm_mat(A, ans, temp);
            copiere(ans, temp);
        }


        inm_mat(A, A, temp);
        copiere(A, temp);

        n /= 2;
    }
    copiere(A, ans);
}


int main()
{
    int k;
    ///int A = {{0, 1}, {1, 1}};
    int A[2][2] = {{0, 1}, {1, 1}};
    fin >> k;
    ridicare(A, k);
    /*for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++)
            cout << A[i][j] << " ";
        cout <<"\n";
    }*/
    fout << A[0][1] % 666013;
    return 0;
}