#include <iostream>
#include <fstream>
constexpr int MOD = 666013;
std::ifstream in("kfib.in");
std::ofstream out("kfib.out");
int fibo[2][1] =
{
    {1},
    {0}
};

int mult[2][2] =
{
    {1, 1},
    {1, 0}
};
int temp[2][2];
void PetruMusat()
{
    for ( int i = 0; i < 2; ++i )
        for ( int j = 0; j < 2; ++j )
        {
            long long s = 0;
            for ( int k = 0; k < 2; ++k )
                s+=(1LL*mult[i][k]%MOD * mult[k][j]%MOD)%MOD, s%=MOD;
            temp[i][j] = s;
        }
    for ( int i = 0; i < 2; ++i )
        for ( int j = 0; j < 2; ++j )
           mult[i][j] = temp[i][j];
}

void i1()
{
    for ( int i = 0; i < 2; ++i )
    {
        long long s = 0;
        for ( int j = 0; j < 2; ++j  )
            s+= (1LL*fibo[j][0]%MOD * mult[i][j]%MOD)%MOD, s%=MOD;
        temp[i][0] = s;
    }
    for ( int i = 0; i < 2; ++i )
        fibo[i][0] = temp[i][0];

}
void TudorAparaschivei(int n)
{
    while(n)
    {
        if ( n % 2 == 1 )
            i1();
        PetruMusat();
        n/=2;
    }
}
int main()
{
    int n;
    in >> n;
    TudorAparaschivei(n - 1);
    out << fibo[0][0];


    return 0;
}