#include <iostream>
#include <fstream>
#define MOD 666013
using namespace std;
long long rez[3][3], i[3][3],  k, crez[3][3], ci[3][3];
int main()
{   int a, b;
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    rez[1][1]=rez[2][2]=1;
    i[1][2]=i[2][1]=i[2][2]=1;
    f>>k;
    k=k-2;
    while(k!=0)
    {
        if(k%2==1)
        {   for(a=1;a<=2;a++)
                for(b=1;b<=2;b++)
                    crez[a][b]=rez[a][b];
            rez[1][1]=(crez[1][1]*i[1][1]+crez[1][2]*i[2][1])%MOD;
            rez[1][2]=(crez[1][1]*i[1][2]+crez[1][2]*i[2][2])%MOD;
            rez[2][1]=(crez[2][1]*i[1][1]+crez[2][2]*i[2][1])%MOD;
            rez[2][2]=(crez[2][1]*i[1][2]+crez[2][2]*i[2][2])%MOD;
            k--;
        }
        else {
            k=k/2;
            for(a=1;a<=2;a++)
                for(b=1;b<=2;b++)
                    ci[a][b]=i[a][b];
            i[1][1]=(ci[1][1]*ci[1][1]+ci[1][2]*ci[2][1])%MOD;
            i[1][2]=(ci[1][1]*ci[1][2]+ci[1][2]*ci[2][2])%MOD;
            i[2][1]=(ci[2][1]*ci[1][1]+ci[2][2]*ci[2][1])%MOD;
            i[2][2]=(ci[2][1]*ci[1][2]+ci[2][2]*ci[2][2])%MOD;
        }
    }
    g<<(rez[1][2]+rez[2][2])%MOD;
    return 0;
}