#include <fstream>
using namespace std;

const int MOD = 666013;
int c[2][2] = {{1, 1},
               {1, 0}};
int sol[2][2] = {{1, 0},
                 {0, 1}};
int n;

void inmMAT(int x[2][2], int y[2][2]) {
    int aux[2][2];
    int i, j, k;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++) {
            aux[i][j] = 0;
            for (k = 0; k < 2; k++)
                aux[i][j] = (aux[i][j] + (1LL * x[i][k] * y[k][j]) % MOD) % MOD;
        }
 
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            x[i][j] = aux[i][j];
}
void exp(int sol[2][2], int k) {
    while (k) {
        if (k % 2 == 1)
            inmMAT(sol, c);
        inmMAT(c, c);
        k /= 2;
    }
}
int main() {

    ifstream f("kfib.in");
    f >> n;
    f.close();

    exp(sol, n - 2);

    ofstream g("kfib.out"); 
    if (n == 0)
        g << 0;
    else if (n == 1 || n == 2)
        g << 1;
    else 
        g << sol[0][0] + sol[0][1];
    g.close();

    return 0;
}