#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 666013
using namespace std;
int M[5][5],X[5][5],n;

void Mul(int a[][5],int b[][5])
{
    int k,i,j;
    int aux[5][5]={0};
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            for (k = 0; k < 2; k++)
                aux[i][j] = (aux[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
    memcpy(a,aux,sizeof(aux));
}

void lgput(int M[][5],int b)
{
    while(b)
        if(b%2==1)
        {
            Mul(X,M);
            b--;
        }
        else
        {
            Mul(M,M);
            b/=2;
        }
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    M[0][0]=0;  M[0][1]=1;  M[1][0]=1;  M[1][1]=1;
    X[0][0]=1; X[1][1]=1;
    lgput(M,n-1);
    printf("%d\n",X[1][1]);
    return 0;
}