#include <fstream>

using namespace std;

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

constexpr int MOD = 666013;

int K;

int a[2][2] = {{0, 1}, {1, 1}};
int n[2][2] = {{1, 0}, {0, 1}};


void LgPut (int K) {
    while (K) {
        if (K % 2 == 0) {
            int aux[2][2] = {{0, 0}, {0, 0}};

            for (int i = 0; i < 2; ++ i )
                for (int j = 0; j < 2; ++ j )
                    for (int k = 0; k < 2; ++ k )
                        aux[i][j] = (aux[i][j] + (1LL * a[i][k] * a[k][j]) % MOD) % MOD;

            for (int i = 0; i < 2; ++ i )
                for (int j = 0; j < 2; ++ j )
                    a[i][j] = aux[i][j];

            K /= 2;
        }
        else {
            int aux[2][2] = {{0, 0}, {0, 0}};

            for (int i = 0; i < 2; ++ i )
                for (int j = 0; j < 2; ++ j )
                    for (int k = 0; k < 2; ++ k )
                        aux[i][j] = (aux[i][j] + (1LL * a[i][k] * n[k][j]) % MOD) % MOD;

            for (int i = 0; i < 2; ++ i )
                for (int j = 0; j < 2; ++ j )
                    n[i][j] = aux[i][j];
            -- K;
        }
    }

    int aux[1][2] = {0, 1};
    int ans[1][2] = {0, 0};

    for (int i = 0; i < 1; ++ i )
        for (int j = 0; j < 2; ++ j )
            for (int k = 0; k < 2; ++ k )
                ans[i][j] = (ans[i][j] + aux[i][k] * n[k][j]) % MOD;

    g << ans[0][0] << '\n';
}

int main()
{
    f >> K;

    LgPut(K);

    return 0;
}