#include <fstream>
#include <cstring>
#define mod 666013
#define N 2

using namespace std;

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

struct matrix
{
    int m[N][N];

    matrix()
    {
        memset(m, 0, sizeof(m));
    }

    matrix operator * (matrix b)
    {
        matrix c;

        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                for (int k = 0; k < N; ++k)
                    c.m[i][j] = ( c.m[i][j] + 1LL * m[i][k] * b.m[k][j] ) % mod;
        return c;
    }
};

matrix unit, a, b;
int k;

matrix mpow (matrix m, int n)
{
    if ( n == 0 )
       return unit;

    matrix half = mpow(m, n / 2);
    matrix out = half * half;

    if ( n % 2 )
       out = out * m;
    return out;
}

int main()
{
    unit.m[0][0] = unit.m[1][1] = 1;

    a.m[0][0] = a.m[0][1] = 1;

    b.m[0][1] = b.m[1][0] = b.m[1][1] = 1;

    f >> k;
    matrix c = mpow(b, k);

    g << c.m[0][1];
    return 0;
}