#include <cstdio>
#define MOD 666013

using namespace std;

int n,i,j,put,k;
int a[3][3],aux[3][3];

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    a[1][1]=0;a[1][2]=1;
    a[2][1]=1;a[2][2]=1;
    aux[1][1]=1;aux[2][2]=1;
    put=n;
    while(put > 0)
    {
        if(put % 2 == 0)
        {
            //inmultim pe a cu a
            int rez[3][3]={0};
            for(i=1;i<=2;++i)
                for(j=1;j<=2;++j)
                    for(k=1;k<=2;++k)
                        rez[i][j] = ((1ll*a[i][k]*a[k][j])%MOD + rez[i][j]) %MOD;

            for(i=1;i<=2;++i)
                for(j=1;j<=2;++j) a[i][j]=rez[i][j];
            put = put/2;
        }
        else
        {
            //I2 = I2 * a
              int rez[3][3] = {0};
            for(int i = 1; i <= 2; ++i)
                for(int j = 1; j <= 2; ++j)
                    for(int k = 1; k <= 2; ++k)
                    {
                        rez[i][j] = ( (1ll * aux[i][k] * a[k][j])%MOD + rez[i][j]) % MOD;
                    }
            for(int i = 1; i <= 2; i++)
                for(int j = 1; j <= 2; j++)
                    aux[i][j] = rez[i][j];
            put = put-1;
        }
    }
    printf("%d\n",aux[1][2]%MOD);
    return 0;
}