#include <cstdio>

using namespace std;
int fib[2][2],aux[2][2],z[2][2];
int n;
void inmultire(int x[][2],int y[][2]){
    int p[2][2];

    for(int i = 0; i < 2; ++i){

        for(int j = 0; j < 2; ++j){
            int s = 0;
            for(int k = 0; k < 2; ++k){
                s = s + 1LL * x[i][k] * y[j][k] % 666013;
            }
            p[i][j] = s % 666013;
        }
    }
    for(int i = 0; i < 2; ++i){
        for(int j = 0; j < 2; ++j){
            x[i][j] = p[i][j];
        }
    }
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    n--;
    fib[0][0] = 1; fib[0][1] = 1;
    aux[1][1] = 1; aux[0][0] = 0; aux[1][0] = 1; aux[0][1] = 1;
    z[1][1] = 1; z[0][0] = 1;
    while(n){
        if(n % 2){
            n--;
            inmultire(z,aux);
        }
        n/=2;
        inmultire(aux,aux);
    }
    inmultire(fib,z);
    printf("%d",fib[0][0] % 666013);
    return 0;
}