#include <iostream>
#include <cstdio>
using namespace std;
int t,n;
struct matrice
{
    long long ms[2][2];
    matrice()
    {
        ms[0][0]=1;
        ms[0][1]=0;
        ms[1][0]=0;
        ms[1][1]=1;
    }
    matrice& operator*(matrice m2)
    {
        matrice rez;
        rez.ms[0][0]=(ms[0][0]*m2.ms[0][0]%666013+ms[0][1]*m2.ms[1][0]%666013)%666013;
        rez.ms[0][1]=(ms[0][0]*m2.ms[0][1]%666013+ms[0][1]*m2.ms[1][1]%666013)%666013;
        rez.ms[1][0]=(ms[1][0]*m2.ms[0][0]%666013+ms[1][1]*m2.ms[1][0]%666013)%666013;
        rez.ms[1][1]=(ms[1][0]*m2.ms[0][1]%666013+ms[1][1]*m2.ms[1][1]%666013)%666013;
        return rez;
    }
};
int fib(int put,matrice m)
{
    matrice rez;
    while(put)
    {
        if(put%2)
        {
            rez=rez*m;
            put--;
        }
        m=m*m;
        put/=2;
    }
    return rez.ms[1][1]%666013;
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d%d",&n);
    matrice f;
    f.ms[0][0]=0;
    f.ms[0][1]=1;
    f.ms[1][0]=1;
    f.ms[1][1]=1;
    if(n==1)
        printf("0");
    if(n==2)
        printf("1");
    if(n>2)
        printf("%lld",fib(n-1,f));
    return 0;
}