#include <iostream>
#include <cstdio>
#define MOD 666013
using namespace std;
long long f[3][3],g[3][3],h[3][3],h1[3][3],x,k,i,m,j,ct,n;
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%lld",&x);
    g[1][1]=h[1][1]=1;
    g[1][2]=h[1][2]=1;
    g[2][1]=h[2][1]=1;
    g[2][2]=h[2][2]=0;
    f[1][1]=f[2][2]=1;
    for(j=x-1;j!=1;)
    {
       if(j%2==0)
       {
        h1[1][1]=((g[1][1]*g[1][1])%MOD+(g[1][2]*g[2][1])%MOD)%MOD;
        h1[1][2]=((g[1][1]*g[1][2])%MOD+(g[1][2]*g[2][2])%MOD)%MOD;
        h1[2][1]=((g[1][1]*g[2][1])%MOD+(g[2][1]*g[2][2])%MOD)%MOD;
        h1[2][2]=((g[1][2]*g[2][1])%MOD+(g[2][2]*g[2][2])%MOD)%MOD;
        g[1][1]=h1[1][1];
        g[1][2]=h1[1][2];
        g[2][1]=h1[2][1];
        g[2][2]=h1[2][2];
       j/=2;
       }
       else
       {
            j--;
            h[1][1]=((f[1][1]*g[1][1])%MOD+(f[1][2]*g[2][1])%MOD)%MOD;
            h[1][2]=((f[1][1]*g[1][2])%MOD+(f[1][2]*g[2][2])%MOD)%MOD;
            h[2][1]=((f[1][1]*g[2][1])%MOD+(f[2][1]*g[2][2])%MOD)%MOD;
            h[2][2]=((f[1][2]*g[2][1])%MOD+(f[2][1]*g[2][2])%MOD)%MOD;
            f[1][1]=h[1][1];
            f[2][1]=h[2][1];
            f[1][2]=h[1][2];
            f[2][2]=h[2][2];
       }
    }/*
    for(k=1;k<=2;k++)
        cout<<f[k][1]<<" "<<f[k][2]<<endl;
    cout<<endl;
    for(k=1;k<=2;k++)
        cout<<g[k][1]<<" "<<g[k][2]<<endl;
    */g[1][1]=((g[1][1]*f[1][1])%MOD+(g[2][1]*f[1][2])%MOD)%MOD;
    printf("%lld\n",g[1][1]%MOD);
    //cout<<g[1][1]<<" "<<f[1][1]<<endl;
    return 0;
}