#include<fstream>
#include<cmath>
#define q sqrt(5)
std::ifstream f("fibonacci.in");std::ofstream g("fibonacci.out");
int main()
{
    int n;
    f>>n;
    g<<(uint64_t)(pow((1+q)/2,n)/q)%666013;
}