#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int modulo = 666013;

ll M[2][2] = {{0,1},
              {1,1}};

ll F[2][2] = {{0,0},
              {0,1}};

void multiply(ll A[][2], ll B[][2]) {
    ll temp[2][2];
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++) {
            ll rez = 0;
            for(int l=0; l<2; l++)
                rez = (rez + A[i][l] * B[l][j]) % modulo;
            temp[i][j] = rez;
        }
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            A[i][j] = temp[i][j];
}

void exp(int n) {
    while(n) {
        if(n%2) multiply(F,M);
        n /= 2;
        multiply(M,M);
    }
}

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

    int n; f >> n;
    exp(n-1);
    g << F[1][1];
    return 0;
}