#include <cstdio>
#define MOD 666013
using namespace std;
long long int M[3][3], A[3][3];
void sum (int n)
{
    long long int i, x1, x2, x3, x4;
    M[1][1]=0; M[1][2]=1; M[2][1]=1; M[2][2]=1;
    for (i=1; i<=n; i++)
    {
        x1=M[1][1]*M[1][1]+M[1][2]*M[2][1];
        x2=M[1][1]*M[1][2]+M[1][2]*M[2][2];
        x3=M[2][1]*M[1][1]+M[2][2]*M[2][1];
        x4=M[2][1]*M[1][2]+M[2][2]*M[2][2];
        M[1][1]=x1%MOD; M[1][2]=x2%MOD; M[2][1]=x3%MOD; M[2][2]=x4%MOD;
    }
    x1=A[1][1]*M[1][1]+A[1][2]*M[2][1];
    x2=A[1][1]*M[1][2]+A[1][2]*M[2][2];
    x3=A[2][1]*M[1][1]+A[2][2]*M[2][1];
    x4=A[2][1]*M[1][2]+A[2][2]*M[2][2];
    A[1][1]=x1%MOD; A[1][2]=x2%MOD; A[2][1]=x3%MOD; A[2][2]=x4%MOD;
}
int main()
{
    int a, k, p, n, i, sol;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&a); A[1][1]=1; A[1][2]=0; A[2][1]=0; A[2][2]=1;
    if (a<3) {printf("%d\n",1%MOD); return 0;}
    else k=a-2; p=k; i=0;
    while (p>0)
    {
        if (p%2==1)
        {
            sum(i);
        }
        p/=2; i++;
    }
    sol=A[1][2]+A[2][2];
    printf("%d\n",sol%MOD);
    return 0;
}