#include <iostream>
#include <fstream>
using namespace std;

#define mod 666013
#define ll long long

ifstream f("kfib.in");
ofstream g("kfib.out");

ll k;
ll a[3][3] , b[3][3] , c[3][3] , x[3][3];

void inmultire ( ll a[3][3] , ll b[3][3] )
{
    ll aux[3][3];
    aux[1][1] = aux[1][2] = aux[2][1] = aux[2][2] = 0;

    for ( int i = 1; i <= 2; i++ )
        for ( int j = 1 ; j <= 2; j++ )
    for ( int d = 1; d <= 2; d++ ) {
                aux[i][j] = ( aux[i][j] + a[i][d] * b[d][j] ) % mod ;
    }
    for ( int i = 1; i <= 2; i++ )
        for ( int j = 1; j <= 2; j++ )
            a[i][j] = aux[i][j];
}

void exp_log ( int k )
{
    while ( k )
    {
        if ( k % 2 == 1 )
        {
            inmultire(x,a);
            k--;
        }
        else
        {
            inmultire(a,a);
            k/=2;
        }
    }
}


int main()
{
    f >> k;

    a[1][1] = 0;
    a[1][2] = a[2][1] = a[2][2] = 1;

    x[1][1] = 1;
    x[2][2] = 1;

    exp_log(k);
    g << x[1][2];

    return 0;
}