// Al k-lea termen Fibonacci.cpp : This file contains the 'main' function. Program execution begins and ends there.
//https://www.infoarena.ro/problema/kfib

#include <iostream>
#include <fstream>

using namespace std;

int mem[666013];

int fib(int n)
{
    int answer;
    if (mem[n])
        return mem[n];
    if (n == 1 || n == 2)
        answer = 1;
    else
    {
        answer = fib(n - 1) + fib(n - 2);
        mem[n] = answer;
    }
    return answer;
}

int main()
{
    int a;
    ifstream f("kfib.in");
    f >> a;
    a = a % 666013;
    ofstream g("kfib.out");
    g << fib(a);
    f.close();
    g.close();
}