#include<cstdio>
using namespace std;
int n;
#define mod 666013
struct mat
{
    long long a11,a12,a21,a22;
};
mat z;
mat lg_pow(int p)
{
    if(p<=1) return z;
    mat ct=lg_pow(p/2);
    mat r;
    r.a11=(ct.a11*ct.a11+ct.a12*ct.a21)%mod;
     r.a12=(ct.a11*ct.a12+ct.a12*ct.a22)%mod;
     r.a21=(ct.a21*ct.a11+ct.a22*ct.a21)%mod;
     r.a22=(ct.a21*ct.a12+ct.a22*ct.a22)%mod;
     if(p%2==1)
     {
         ct=r;
         r.a11=ct.a12;
         r.a12=(ct.a11+ct.a12)%mod;
         r.a21=ct.a22;
         r.a22=(ct.a21+ct.a22)%mod;
     }
     return r;
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    scanf("%d",&n);
    z.a11=0;
    z.a12=z.a21=z.a22=1;
    mat rez=lg_pow(n-1);
    printf("%d",rez.a22);
    return 0;
}