#include <fstream>

using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
long long k, a, b=1, c=1, d=1, x, y, z, w, p1=1, p2, p3, p4=1;
int main()
{
    fin >> k;
    --k;
    while (k>0)
    {
        if (k%2==0)
        {
            x=a*a+b*c;
            y=a*b+b*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=p1*a+p2*c;
            y=p1*b+p2*d;
            z=p3*a+p4*c;
            w=p3*b+p4*d;
            p1=x%666013;
            p2=y%666013;
            p3=z%666013;
            p4=w%666013;
            k--;
        }
    }
    fout << p4%666013;
    return 0;
}