#include <cstdio>
#include <cstring>
#define MOD 666013

long long A[3][3],B[3][3],aux[3][3];
//A se ridica la putere si rezultatul este retinut in B
//aux retine inmultirea diferitelor matrici, fiind apoi copiat in matricea destinatie
int main()
{
    int n;
	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;
    B[1][1]=1; B[1][2]=0; B[2][1]=0; B[2][2]=1;

    for (int i=1; i<=n; i<<=1)
    {
        if (i&n)
        {
            aux[1][1]=((A[1][1]*B[1][1])%MOD+(A[1][2]*B[2][1])%MOD)%MOD;
            aux[1][2]=((A[1][1]*B[1][2])%MOD+(A[1][2]*B[2][2])%MOD)%MOD;
            aux[2][1]=((A[2][1]*B[1][1])%MOD+(A[2][2]*B[2][1])%MOD)%MOD;
            aux[2][2]=((A[2][1]*B[1][2])%MOD+(A[2][2]*B[2][2])%MOD)%MOD;

            memcpy(B,aux,sizeof(aux));
        }
        aux[1][1]=((A[1][1]*A[1][1])%MOD+(A[1][2]*A[2][1])%MOD)%MOD;
        aux[1][2]=((A[1][1]*A[1][2])%MOD+(A[1][2]*A[2][2])%MOD)%MOD;
        aux[2][1]=((A[2][1]*A[1][1])%MOD+(A[2][2]*A[2][1])%MOD)%MOD;
        aux[2][2]=((A[2][1]*A[1][2])%MOD+(A[2][2]*A[2][2])%MOD)%MOD;

        memcpy(A,aux,sizeof(aux));
    }

    printf("%lld",B[1][2]);

    return 0;
}