#include <fstream>
using namespace std;

const long long MOD = 666013;

void inmultire(long long a[2][2], long long b[2][2], long long rez[2][2])
{
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j) {
            rez[i][j] = 0;
            for (int t = 0; t < 2; ++t)
                rez[i][j] = (rez[i][j] + (a[i][t] * b[t][j])%MOD) % MOD;
        }
}


void copiere(long long deunde[2][2], long long unde[2][2])
{
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            unde[i][j] = deunde[i][j];
}


void putere(long long a[2][2], int put, long long rez[2][2])
{
    if (put == 0) {
        rez[0][0] = 1;
        rez[0][1] = 0;
        rez[1][0] = 0;
        rez[1][1] = 1;
    }
    else {
        long long temp[2][2];

        putere(a, put/2, temp);

        inmultire(temp, temp, rez);

        if (put % 2 != 0) {
            copiere(rez, temp);
            inmultire(a, temp, rez);
        }
    }
}


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

    int k;
    fin >> k;

    long long A[2][2] = { {0,1}, {1,1} };
    long long B[2][2];

    if (k == 0)
        fout << 0 << '\n';
    else
        putere(A, k-1, B);

    fout << B[1][1] << '\n';

    return 0;
}