#include <fstream>
#include <iostream>
#define MOD 666013
using namespace std;
ifstream fi("kfib.in");
ofstream fo("kfib.out");
struct Matrix
{
    long long a1, a2, a3,a4;
};

Matrix Multiply(Matrix a, Matrix b)
{
    Matrix rez;
    rez.a1 = (a.a1 * b.a1 + a.a2 * b.a3 )% MOD;
    rez.a2 = (a.a1 * b.a2 + a.a2 * b.a4 )% MOD;
    rez.a3 = (a.a3 * b.a1 + a.a4 * b.a3 )% MOD;
    rez.a4 = (a.a3 * b.a2 + a.a4 * b.a4 )% MOD;
    return rez;
}
Matrix LgPut(Matrix a, int n)
{
    Matrix sol;
    sol.a1 = 1;
    sol.a2 = 0;
    sol.a3 = 0;
    sol.a4 = 1;
    while(n)
    {

        if(n & 1)
            sol = Multiply(sol, a);

        n /= 2;
        a = Multiply(a, a);
    }
    return sol;
}

int main()
{
    int k;
    Matrix m;
    m.a1 = 0;
    m.a2 = 1;
    m.a3 = 1;
    m.a4 = 1;
    fi>>k;
    m = LgPut(m, k - 1);
    fo<<m.a4;

}