#include <fstream>
#define MOD 666013
using namespace std;

inline void inmulteste(int matrix1[][2], int matrix2[][2], int resultValue[][2])
{
    int i, j, k;
    for (i=0;i<=1;++i)
        for (j=0;j<=1;++j)
            for (k=0;k<=1;++k)
                resultValue[i][j] = (resultValue[i][j] + (unsigned long long)matrix1[k][j]*matrix2[i][k])%MOD;
    matrix1[0][0] = resultValue[0][0]; matrix1[0][1] = resultValue[0][1]; matrix1[1][0] = resultValue[1][0]; matrix1[1][1] = resultValue[1][1];
}

void lgPower(int m[2][2], int pow)
{
    int matrix[2][2] = {{0, 1}, {1, 1}}, aux[2][2], i;
    for (i=0;1<<i <= pow; ++i)
    {
        aux[0][0] = aux[0][1] = aux[1][0] = aux[1][1] = 0;
        if (1<<i & pow)
            inmulteste(m, matrix, aux);
        aux[0][0] = aux[0][1] = aux[1][0] = aux[1][1] = 0;
        inmulteste(matrix, matrix, aux);
    }
}

int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    int n, matrix[2][2] = {{1, 0}, {0, 1}};
    f >> n;
    lgPower(matrix, n-1);
    g << matrix[1][1];
    return 0;
}