#include <fstream>

using namespace std;
ifstream fin ("kfibo.in");
ofstream fout ("kfibo.out");
int k, a, b=1, c=1, d=1, x, y, z, w;
int main()
{
    fin >> k;
    k=k-2;
    while (k>0)
    {
        if (!k%2)
        {
            x=a*a+b*c;
            y=a*b+c*d;
            z=a*c+c*d;
            w=b*c+d*d;
            a=x%666013;
            b=y%666013;
            c=z%666013;
            d=w%666013;
            k=k/2;
        }
        else
        {
            x=a;
            y=a+b;
            z=d;
            w=c+d;
            a=x%666013;
            b=y%666013;
            c=z%666013;
            d=w%666013;
            k--;
        }
    }
    fout << d;
    return 0;
}