#include <cstdio>

#define mod 666013

using namespace std;

long long rez[2][2];

void explog (long long a[2][2], int e)
{
    long long aux1,aux2,aux3,aux4;
    while (e!=0)
    {
        if (e%2==0)
        {
            aux1=((a[0][0]*a[0][0])%mod+(a[0][1]*a[1][0])%mod)%mod;
            aux2=((a[0][0]*a[0][1])%mod+(a[0][1]*a[1][1])%mod)%mod;
            aux3=((a[1][0]*a[0][0])%mod+(a[1][1]*a[1][0])%mod)%mod;
            aux4=((a[1][0]*a[0][1])%mod+(a[1][1]*a[1][1])%mod)%mod;
            a[0][0]=aux1;
            a[0][1]=aux2;
            a[1][0]=aux3;
            a[1][1]=aux4;
            e/=2;
        }
        else
        {
            aux1=((rez[0][0]*a[0][0])%mod+(rez[0][1]*a[1][0])%mod)%mod;
            aux2=((rez[0][0]*a[0][1])%mod+(rez[0][1]*a[1][1])%mod)%mod;
            aux3=((rez[1][0]*a[0][0])%mod+(rez[1][1]*a[1][0])%mod)%mod;
            aux4=((rez[1][0]*a[0][1])%mod+(rez[1][1]*a[1][1])%mod)%mod;
            rez[0][0]=aux1;
            rez[0][1]=aux2;
            rez[1][0]=aux3;
            rez[1][1]=aux4;
            e--;
        }
    }
}

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

    int k;
    scanf ("%d",&k);

    long long A[2][2];
    A[0][0]=0;
    A[0][1]=A[1][0]=A[1][1]=1;

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

    explog (A,k-1);

    printf ("%lld",rez[1][1]);

    return 0;
}