#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;

map <int, int> F;

int fib( int n )
{
    if ( F.count( n ) )
        return F[n];

    int k = n >> 1;

    if ( n % 2 == 0 )
        return F[n] = ( 1LL * fib( k ) * fib( k ) + 1LL * fib( k - 1 ) * fib( k - 1 ) ) % MOD;
    else
        return F[n] = ( 1LL * fib( k - 1 ) * fib( k ) + 1LL * fib( k ) * fib( k + 1 ) ) % MOD;
}

int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");

    int K;

    F[0] = F[1] = 1;

    in >> K;
    out << fib( K - 1 ) << "\n";

    return 0;
}