#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

#define MOD 666013

long long n, x1, x2, x3, x4, y1, y2, y3, y4;

void putere( int p )
{
    if ( p == 1 )
    {
        x1 = 0; x2 = 1; x3 = 1; x4 = 1;
    }
    else
    {
        putere( p / 2 );
        y1 = x1 * x1 + x2 * x3;
        y2 = x1 * x2 + x2 * x4;
        y3 = x3 * x1 + x4 * x3;
        y4 = x3 * x2 + x4 * x4;
        x1 = y1 % MOD; x2 = y2 % MOD; x3 = y3 % MOD; x4 = y4 % MOD;
        if( p % 2 == 1 )
        {
            y1 = x1 * 0 + x2 * 1;
            y2 = x1 * 1 + x2 * 1;
            y3 = x3 * 0 + x4 * 1;
            y4 = x3 * 1 + x4 * 1;
            x1 = y1 % MOD; x2 = y2 % MOD; x3 = y3 % MOD; x4 = y4 % MOD;
        }
    }
}

int main ()
{
    fin >> n;
    if ( n == 0 )
        fout<< 0;
    else
    {
        putere( n );
        fout<< x3;
    }
}