#include <fstream>

using namespace std;
long long k,p[4][4],v[4][4],c[4][4];
int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");

    f>>k;
    k--;
    v[1][1]=1;v[1][2]=1;v[2][1]=1;
    p[1][1]=1;p[2][2]=1;
    while(k)
    {
        if(k%2==1)
        {
    c[1][1]=(p[1][1]*v[1][1]+p[1][2]*v[2][1])%666013;
    c[1][2]=(p[1][1]*v[1][2]+p[1][2]*v[2][2])%666013;
    c[2][1]=(p[2][1]*v[1][1]+p[2][2]*v[2][1])%666013;
    c[2][2]=(p[2][1]*v[1][2]+p[2][2]*v[2][2])%666013;
    p[1][1]=c[1][1];p[1][2]=c[1][2];p[2][1]=c[2][1];p[2][2]=c[2][2];
    k--;
        }
    c[1][1]=(v[1][1]*v[1][1]+v[1][2]*v[2][1])%666013;
    c[1][2]=(v[1][1]*v[1][2]+v[1][2]*v[2][2])%666013;
    c[2][1]=(v[2][1]*v[1][1]+v[2][2]*v[2][1])%666013;
    c[2][2]=(v[2][1]*v[1][2]+v[2][2]*v[2][2])%666013;
    v[1][1]=c[1][1];v[1][2]=c[1][2];v[2][1]=c[2][1];v[2][2]=c[2][2];
        k=k/2;
    }
    g<<(p[2][1]+p[2][2])%666013;
    return 0;
}