#include <iostream>
#include <fstream>
#define pr(x,y,z,t) ((long long)x%666013*(y%666013)+(long long)z%666013*(t%666013))%666013
using namespace std;

int main()
{
    fstream ff("kfib.in",ios::in);
    int n,a=1,b=1,c=1,d=0,a1,b1,c1,d1,e=1,f=0,g=0,h=1,e1,f1,g1,h1;
    ff>>n;
    n--;
    while(n)
    {
        if(n%2)
        {
            e1=pr(a,e,c,f);
            f1=pr(b,e,d,f);
            g1=pr(a,g,c,h);
            h1=pr(b,g,d,h);
            e=e1;f=f1;g=g1;h=h1;
        }
        n/=2;
        a1=pr(a,a,b,c);
        b1=pr(a,b,b,d);
        c1=pr(a,c,c,d);
        d1=pr(b,c,d,d);
        a=a1;b=b1;c=c1;d=d1;
    }
    ff.close();
    ff.open("kfib.out",ios::out);
    ff<<e;
    return 0;
}