#include <cstdio>
#define mod 666013
using namespace std;
long long I[3][3], CI[3][3], rez[3][3], f[2][3];
void ridiclaput(int exp)
{
    int i, j;
    rez[1][1]=1;
    rez[2][2]=1;
    while(exp)
    {
        if(exp%2==0)
        {
            CI[1][1]=(I[1][1]*I[1][1]+I[1][2]*I[2][1])%mod;
            CI[1][2]=(I[1][1]*I[1][2]+I[1][2]*I[2][2])%mod;
            CI[2][1]=(I[2][1]*I[1][1]+I[2][2]*I[2][1])%mod;
            CI[2][2]=(I[2][1]*I[1][2]+I[2][2]*I[2][2])%mod;
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    I[i][j]=CI[i][j];
            exp/=2;
        }
        else{
            CI[1][1]=(rez[1][1]*I[1][1]+rez[1][2]*I[2][1])%mod;
            CI[1][2]=(rez[1][1]*I[1][2]+rez[1][2]*I[2][2])%mod;
            CI[2][1]=(rez[2][1]*I[1][1]+rez[2][2]*I[2][1])%mod;
            CI[2][2]=(rez[2][1]*I[1][2]+rez[2][2]*I[2][2])%mod;
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    rez[i][j]=CI[i][j];
            exp--;
        }
    }
}
int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out","w", stdout);
    int n;
    scanf("%d", &n);
    f[1][1]=0;
    f[1][2]=1;
    I[2][1]=1;
    I[1][2]=1;
    I[2][2]=1;
    ridiclaput(n-1);
    CI[1][1]=(f[1][1]*rez[1][1]+f[1][2]*rez[2][1])%mod;
    CI[1][2]=(f[1][1]*rez[1][2]+f[1][2]*rez[2][2])%mod;
    printf("%lld", CI[1][2]);
    return 0;
}