#include <cstdio>
#define MOD 666013
using namespace std;
/**
a -> (Fn-1 Fn)
cop-> (1 1
       1 0)
*/
long long a[3][3];
long long cop[3][3];
long long rez[3][3];
int k;
void inmultire(long long a1[3][3], long long b[3][3], long long c[3][3])
{
    c[1][1]=0;
    c[1][2]=0;
    c[2][1]=0;
    c[2][2]=0;
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            int s=0;
            for(int k=1; k<=2; k++)
                c[i][j]=(c[i][j]+((1LL*a1[i][k]*b[k][j])%MOD))%MOD;
        }
    }
}
void inloc(long long a1[3][3], long long b[3][3])
{
    a1[1][1]=b[1][1];
    a1[1][2]=b[1][2];
    a1[2][1]=b[2][1];
    a1[2][2]=b[2][2];
    for(int i=1;i<=2; i++)
        for(int j=1;j<=2;j++)
        {
            b[i][j]=0;
        }
}
long long rid_putere(int p){

    cop[1][1]=1; cop[1][2]=1;
    cop[2][1]=1; cop[2][2]=0;

    rez[1][1]=1; rez[1][2]=0;
    rez[1][2]=0; rez[2][2]=1;

    while(p){
        if(p%2==1){
            p--;
            inmultire(rez,cop,a);
            inloc(rez,a);
        }
        p/=2;
        inmultire(cop,cop,a);
        inloc(cop,a);
    }
    return (1LL*rez[1][1]+rez[1][2])%MOD;
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d", &k);
    printf("%d",rid_putere(k-2));
    return 0;
}