#include <fstream>
#include <cstdio>
#include <cstring>
#define MOD 666013
#define LL long long
using namespace std;

ofstream g("kfib.out");

int n,v[4];

void mul(int v[],int v2[])
{
    int rez[4];
    rez[0] = ((LL)v[0]*v2[0]+(LL)v[1]*v2[2])%MOD;
    rez[1] = ((LL)v[0]*v2[1]+(LL)v[1]*v2[3])%MOD;
    rez[2] = ((LL)v[2]*v2[0]+(LL)v[3]*v2[2])%MOD;
    rez[3] = ((LL)v[2]*v2[1]+(LL)v[3]*v2[3])%MOD;
    memcpy(v,rez,sizeof(rez));
}

void put(int v[],int e)
{
    if (e==1)
        return;
    else if (e%2==1)
    {
        int v2[4];
        memcpy(v2,v,sizeof(v2));
        mul(v,v);
        put(v,e/2);
        mul(v,v2);
    }
    else
    {
        mul(v,v);
        put(v,e/2);
    }
}

int main()
{
    freopen("kfib.in","r",stdin);
    scanf("%d",&n);

    v[0]=v[1]=v[2]=1;

    put(v,n);

    g<<v[1];


    return 0;
}