#include <fstream>
#define MOD 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int n,a[3][3],aux[3][3],sol[3][3];
 void copiaza ( int a[3][3], int b[3][3] ){
    for ( int i = 1; i <= 2; i++ )
        for ( int j = 1; j <= 2; j++ )
            a[i][j] = b[i][j];
}

void inmulteste ( int a[][3], int b[][3], int c[][3] )
{   for ( int i = 1; i <= 2; i++ )
        for ( int j=1; j <= 2; j++ )
        {   c[i][j] = 0;
            for ( int k = 1; k <= 2; k++ )
                c[i][j] = (c[i][j]+1LL*a[i][k]*b[k][j])%MOD;
        }
}
int main()
{   f>>n;
    if ( n <= 1 ) g<<n;
    else
    {   n--;
        a[1][1] = a[1][2] = a[2][1] = 1;
        sol[1][1] = sol[2][2] = 1;
        while (n) {
            if ( n%2 )
            {   inmulteste ( a, sol, aux );
                copiaza ( sol, aux );
            }
            inmulteste ( a, a, aux );
            copiaza ( a, aux );
            n /= 2;
        }
        g<<sol[1][1];
    }
    g.close();
    f.close();
    return 0;
}