#include <cstdio>

using namespace std;

#define IN "kfib.in"
#define OUT "kfib.out"
#define mod 666013

int a[2][2] , princ[2][2];
int n;

void Multiply1()
{
    int aa , b , c , d;
        aa = princ[0][0];
        b = princ[0][1];
        c = princ[1][0];
        d = princ[1][1];

         princ[0][0] = (1LL*aa*a[0][0]+1LL*b*a[1][0])%mod;
         princ[0][1] = (1LL*aa*a[0][1]+1LL*b*a[1][1])%mod;
         princ[1][0] = (1LL*c*a[0][0]+1LL*d*a[1][0])%mod;
         princ[1][1] = (1LL*c*a[0][1]+1LL*d*a[1][1])%mod;
}
void Multiply2()
{
    int aux[2][2];

    int i , j , aa , b , c , d;

    for ( i = 0 ; i <= 1 ; i ++ )
        for ( j = 0 ; j <= 1 ; j ++ )
            aux[i][j] = a[i][j];

    aa = a[0][0];
    b = a[0][1];
    c = a[1][0];
    d = a[1][1];
         a[0][0] = (1LL*aa*aux[0][0]+1LL*b*aux[1][0])%mod;
         a[0][1] = (1LL*aa*aux[0][1]+1LL*b*aux[1][1])%mod;
         a[1][0] = (1LL*c*aux[0][0]+1LL*d*aux[1][0])%mod;
         a[1][1] = (1LL*c*aux[0][1]+1LL*d*aux[1][1])%mod;


}

void Solve()
{
    int put;
    a[0][1] = a[1][0] = a[1][1] = 1;
    princ[0][0] = princ[1][1] = 1;
    scanf ( "%d" , &n );

    put = n-1;
    while(put>0)
    {
        if(put&1)
            Multiply1() , put--;
        Multiply2() , put >>= 1;
    }

    printf ( "%d" , princ[1][1] );

}

int main()
{
    freopen(IN,"r",stdin);
    freopen(OUT,"w",stdout);

    Solve();
}