#include <iostream>
#include <fstream>

#define MOD 666013

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

using namespace std;

typedef unsigned long long ull;

struct matrix{
    ull mat[2][2];

    matrix(ull a, ull b, ull c, ull 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] + 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

    while(exp != 0)
    {
        if(exp % 2 == 0)
            result = multiply(a, result);

        a = multiply(a, a);
        exp /= 2;
    }

    return result;
}

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

    in >> n;

    fibo = lgPut(fibo, n - 1);

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