// 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];
long long mod = 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;
//}

long long fib2(long long n)
{
    long long a, b, answer;
    if (n==1 || n==2)
        return 1;
    a = 1;
    b = 1;
    for (long long i = 3; i <= n; i++)
    {
        answer = a + b;
        a = b;
        b = answer;
    }
        //mem[i] = mem[i - 1] + mem[i - 2];
    return answer;
}



int main()
{
    long long a, b;

    /*cin >> a;
    a = a ;
    cout << fib2(a) % mod;*/

    ifstream f("kfib.in");
    f >> a;
    //a = a % 666013;
    ofstream g("kfib.out");
    b=fib2(a) % mod;
    g << b;
    f.close();
    g.close();

    }