#include <iostream>
#include <fstream>

#define MOD 666013

std::ifstream in("kfib.in");
std::ofstream out("kfib.out");

using namespace std;

typedef long long ll;

struct matrix{
    ll mat[3][3];

    matrix(ll a, ll b, ll c, ll d)
    {
        mat[0][0] = a;
        mat[0][1] = b;
        mat[1][0] = c;
        mat[1][1] = d;
    }
};

matrix multiply(matrix a, matrix b)
{
    matrix result = matrix(0, 0, 0, 0);

    for(int i = 0; i <= 1; i++)
        for(int j = 0; j <= 1; j++)
            for(int k = 0; k <= 1; k++)
                result.mat[i][j] = (result.mat[i][j] + 1LL * a.mat[i][k] * b.mat[k][j]) % MOD;

    return result;
}

matrix lgPut(matrix a, int exp)
{
    matrix result = matrix(1, 0, 0, 1); /// = I2

   	for (int i = 0; (1 << i) <= exp; i++)
    {
        if(exp & (1 << i))
            result = multiply(result, a);

        a = multiply(a, a);
    }

    return result;
}

int main()
{
    int n;
    matrix fibo = matrix(0, 1, 1, 1);

    in >> n;

    fibo = lgPut(fibo, n - 1);

    out << (fibo.mat[1][1]) % MOD;
    return 0;
}