#include <cstdio>
#include <cstring>
#define mod 666013

using namespace std;

FILE *fin=freopen("kfib.in","r",stdin);
FILE *fout=freopen("kfib.out","w",stdout);

int n,mat[3][3],sol[3][3];

void mult(int a[][3],int b[][3], int c[][3])
{
    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 putere(int m[][3],int p)
{
    int c[3][3],aux[3][3];
    for(int i=0;i<2;i++)
        for(int j=1;j<2;j++)
            c[i][j]=mat[i][j];
    m[0][0] = m[1][1] = 1;
    for (int i = 0; (1 << i) <= p; i++) {
        if (p & (1 << i)) {
            memset(aux, 0, sizeof(aux));
            mult(m, c, aux);
            memcpy(m, aux, sizeof(aux));
        }

        memset(aux, 0, sizeof(aux));
        mult(c, c, aux);
        memcpy(c, aux, sizeof(c));
    }
}

int main()
{
    scanf("%d",&n);
    mat[0][0]=0;
    mat[0][1]=mat[1][0]=mat[1][1]=1;
    putere(sol,n-1);
    printf("%d\n",sol[1][1]);
    return 0;
}