#include <fstream>

using namespace std;

int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");

    long long a;
    long long b;
    in >> a;
    b = 666013;

    long long x1 = 1, x2 = 1;
    for (long long i = 3; ; ++i)
    {
        x2 = x1 + x2;
        x1 = x2 - x1;
        x2 %= b;
        if (x1 == 1 && x2 == 1)
        {
            a %= (i-2);
            break;
        }
    }

    x1 = x2 = 1;
    for (int i = 3; i <= a; ++i)
    {
        x2 = x1 + x2;
        x1 = x2 - x1;
        x2 %= b;
    }

    out << x2 << '\n';


    return 0;
}