#include <cstdio>
#define MOD 666013

using namespace std;

int k;
int a[4][4], m[4][4], rez[4][4];

void copiere(int a[4][4], int c[4][4])
{
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
            a[i][j]=c[i][j];
    }
}

void inmultire(int a[4][4], int b[4][4])
{
    int c[4][4]={0};
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            for(int nr=1; nr<=2; nr++)
                c[i][j]=(c[i][j]+((1LL*a[i][nr]*b[nr][j])%MOD))%MOD;
        }
    }
    copiere(a, c);
}



void ridicare(int putere)
{
    copiere(rez, m);
    putere--;
    while(putere)
    {
        if(putere%2)
        {
            putere--;
            inmultire(rez, m);
        }
        putere/=2;
        inmultire(m, m);
    }
}

int main()
{

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

    scanf("%d", &k);
    m[1][1]=1;
    m[1][2]=1;
    m[2][1]=1;
    m[2][2]=0;

    ridicare(k-1);
    printf("%d", rez[1][1]);

    return 0;
}