#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;

}