#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#define mod 666013
using namespace std;
ofstream g("kfib.out");
int a[3][3],r[3][3],x[3][3],i,j,k;
void inmulteste(int z[3][3],int a[3][3])
{
    for(int ii=1;ii<=2;ii++)
    {
        for(int jj=1;jj<=2;jj++)
        {
            x[ii][jj]=0;
        }
    }
    for(int ii=1;ii<=2;ii++)
    {
        for(int jj=1;jj<=2;jj++)
        {
            for(int ct=1;ct<=2;ct++)
            {
                x[ii][jj]+=1LL*z[ii][ct]*a[ct][jj]%mod;
            }
        }
    }
}
int main()
{
    freopen("kfib.in","r",stdin);
    a[1][1]=1;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=0;
    r[1][1]=1;
    r[1][2]=0;
    r[2][1]=0;
    r[2][2]=1;
    scanf("%d",&k);
    if(k<=2)
    {
        g<<1;
        return 0;
    }
    k-=2;
    while(k)
    {
        if(k&1)
        {
            inmulteste(r,a);
            memcpy(r,x,36);
        }
        inmulteste(a,a);
        memcpy(a,x,36);
        k>>=1;
    }
    g<<(r[1][1]+r[1][2])%mod;
    return 0;
}