#include <cstdio>

using namespace std;
#define NMAX N + 4
#define N 2
#define mod 666013
int n;
long long a[NMAX][NMAX],s[NMAX][NMAX];
void mul (long long b[NMAX][NMAX], long long  c[NMAX][NMAX])
{
    int i,j,k;
    long long d[NMAX][NMAX];
    for (i=1;i<=N;i++)
        for (j=1;j<=N;j++)
        {
            d[i][j]=0LL;
            for (k=1;k<=N;k++)
                d[i][j]=(0LL+d[i][j]+1LL*b[i][k]*c[k][j])%mod;
        }
    for (i=1;i<=N;i++)
        for (j=1;j<=N;j++)
            b[i][j]=d[i][j];
}
int main()
{
    freopen ("kfib.in","r",stdin);
    freopen ("kfib.out","w",stdout);
    scanf ("%d", &n);
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=1;
    s[1][1]=0;
    s[1][2]=1;
    n--;
    while (n>0)
    {
        if (n%2==1)
            mul(s,a);
        mul(a,a);
        n/=2;
    }
    printf ("%d", s[1][2]);
    return 0;
}