#include <bits/stdc++.h>
#define in "kfib.in"
#define out "kfib.out"
#define MOD 666013
using namespace std;

void matrix_mult(int A[2][2], int B[2][2], int C[2][2])
{
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            for(int k = 0; k < 2; ++k)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
}

void matrix_exp(int Rez[2][2], int N)
{
    int net[2][2], aux[2][2];
    net[0][1] = net[1][0] = 0;
    net[0][0] = net[1][1] = 1;
    for(int e = 0; (1<<e) <= N; ++e)
    {
        if(N & (1<<e))
        {
            memset(aux, 0, sizeof(aux));
            matrix_mult(net, Rez, aux);
            memcpy(net, aux, sizeof(aux));
        }
        memset(aux, 0, sizeof(aux));
        matrix_mult(Rez, Rez, aux);
        memcpy(Rez, aux, sizeof(aux));
    }
    memcpy(Rez, net, sizeof(net));
}

int main()
{
    assert(freopen(in, "r", stdin));
    assert(freopen(out,"w", stdout));
    int N;
    assert(scanf("%d", &N));
    int Sol[2][2];
    Sol[0][0] = 0;
    Sol[0][1] = Sol[1][0] = Sol[1][1] = 1;
    matrix_exp(Sol, N-1);
    assert(printf("%d", Sol[1][1]));
    return 0;
}