#include <fstream>
#include <iostream>

using namespace std;

#define MOD 666013

ifstream fin("kfib.in");
ofstream fout("kfib.out");


struct matrix
{
    int kN , kM;
    int U[3][3];
};

matrix res , p , c , C;
long long N;

matrix mul(matrix A,matrix B)
{
    int i,j,k;
    C.kN = A.kN;
    C.kM = B.kM;

    for (i = 1; i <= A.kN ; ++i)
    for (j = 1; j <= B.kM ; ++j)
    {
        C.U[i][j] = 0;
        for (k = 1; k <= A.kM ; ++k)
        C.U[i][j] = (C.U[i][j] + 1ll * A.U[i][k] * B.U[k][j]) % MOD;
    }

    return C;
}

void lgPut()
{
    int i;

    c.kN = 2;
    c.kM = 2;

    c.U[1][2] = c.U[2][1] = c.U[2][2] = 1;

    res.kN = 2;
    res.kM = 2;

    res.U[1][1] = res.U[2][2] = 1;

    for (i=0;i<=30;++i)
    {
        if ((1 << i) & N)
        res = mul(res , c);

        c = mul(c , c);
    }
}

int main()
{

fin >> N;

lgPut();

p.kN = 1;
p.kM = 2;

p.U[1][2] = 1;

p = mul(p , res);

fout << p.U[1][1] << '\n';

return 0;
}