#include <fstream>

using namespace std;

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

const int mod = 666013;

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

void inmult(int a[2][2], int b[2][2]) {
    int i, j, k;
    int c[2][2];

    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++) {
            c[i][j] = 0;
            for (k = 0; k < 2; k++)
                c[i][j] = (c[i][j] + (1LL*a[i][k]*b[k][j])%mod )%mod;
        }

    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            a[i][j] = c[i][j];
}

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

    while (n > 0) {
        if (n%2 == 1)
            inmult(sol, a);
        inmult(a, a);
        n /= 2;
    }
}

int main() {
    f >> n;

    ridicare(n-1);
    g << (sol[0][0] + sol[1][0])%mod;

    return 0;
}