#include <iostream>
#include<fstream>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

struct matr{
    long long v1, v2, v3, v4;
};


struct matrr{
    long long v1, v2;
};

matr orii(matr a, matrr b)
{
    matr c;
    c.v1 = (a.v1* b.v1) % 666013 + (a.v2*b.v2) % 666013;
    c.v2 = (a.v3 * b.v1) % 666013 + (a.v4 * b.v2) % 666013;
    return c;
}

matr ori(matr a, matr b)
{
    matr c;
    c.v1 = (a.v1 * b.v1) % 666013 + (a.v2 * b.v3) % 666013;
    c.v2 = (a.v1 * b.v2) % 666013 + (a.v2 * b.v4) % 666013;
    c.v3 = (a.v3 * b.v1) % 666013 + (a.v4 * b.v3)% 666013;
    c.v4 = (a.v3 * b.v2) % 666013 + (a.v4 * b.v4) % 666013;
    return c;
}

matr lgput(matr a, int p)
{
    matr r  = a;
    p--;
    while (p) {
        if (p % 2 == 1) {
            r = ori(r, a);
            p--;
        }
        else
        {
            a = ori(a, a);
            p/=2;
        }
    }
    return r;
}

int fib(int n)
{
    if(n <= 2)
        return 1;
    matr a = {1, 1, 1, 0};
    matrr b = {1, 1};
    matr c = orii(lgput(a, n-2), b);
    return c.v1;
}
int main()
{
    int n;
    fin >> n;
    fout << fib(n);
    return 0;
}