#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])%666013+(p[1][2]*v[2][1])%666013)%666013;
    c[1][2]=((p[1][1]*v[1][2])%666013+(p[1][2]*v[2][2])%666013)%666013;
    c[2][1]=((p[2][1]*v[1][1])%666013+(p[2][2]*v[2][1])%666013)%666013;
    c[2][2]=((p[2][1]*v[1][2])%666013+(p[2][2]*v[2][2])%666013)%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])%666013+(v[1][2]*v[2][1])%666013)%666013;
    c[1][2]=((v[1][1]*v[1][2])%666013+(v[1][2]*v[2][2])%666013)%666013;
    c[2][1]=((v[2][1]*v[1][1])%666013+(v[2][2]*v[2][1])%666013)%666013;
    c[2][2]=((v[2][1]*v[1][2])%666013+(v[2][2]*v[2][2])%666013)%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])%666013+(p[2][2])%666013)%666013;
    return 0;
}