#include <fstream>
#include <vector>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int Mod = 666013;
long long n, Matrix[5][5], MatrixFib[5][5];
void Matrix_Mult(long long arg1[5][5], long long arg2[5][5])
{
    long long aux[5][5];
    aux[1][1] = aux[0][0] = aux[0][1] = aux[1][0] = 0;
    for(int i = 0; i <2 ; i++)
    {
        for(int j = 0; j <2; j++)
        {
            for(int k = 0; k <2; k++)
            {
                aux[i][j] = (aux[i][j] + arg1[i][k]*arg2[k][j]*1LL)%Mod;
            }
        }
    }
    for(int i = 0; i <= 1; i++)
        for(int j = 0; j <= 1; j++)
            arg1[i][j] = aux[i][j];
}
void Pow(int p)
{
    while(p)
    {
        if(p%2 == 1) Matrix_Mult(MatrixFib, Matrix);
        Matrix_Mult( Matrix, Matrix);
        p = p/2;
    }
}
void Read()
{
    in>>n;
}
void Solve()
{
    Matrix[0][0] = 0;
     Matrix[1][0] = Matrix[0][1] =  Matrix[1][1] = 1;
    MatrixFib[0][0] = MatrixFib[1][1] = 1;
    MatrixFib[1][0] = MatrixFib[0][1] = 0;
    Pow(n-1);
}
void Print()
{
    out<<MatrixFib[1][1]<<'\n';
}
int main()
{
    Read();
    Solve();
    Print();
    return 0;
}