#include <fstream>
using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");
const int MOD=666013;
long long k;
long long x[3][3], y[3][3],z[3][3];

void inmultire(long long a[3][3],long long b[3][3]){
    long long c[3][3];
    c[1][1]=((a[1][1]%MOD)*(b[1][1]%MOD)+(a[1][2]%MOD)*(b[2][1]%MOD))%MOD;
    c[1][2]=((a[1][1]%MOD)*(b[1][2]%MOD)+(a[1][2]%MOD)*(b[2][2]%MOD))%MOD;
    c[2][1]=((a[2][1]%MOD)*(b[1][1]%MOD)+(a[2][2]%MOD)*(b[2][1]%MOD))%MOD;
    c[2][2]=((a[2][1]%MOD)*(b[1][2]%MOD)+(a[2][2]%MOD)*(b[2][2]%MOD))%MOD;
    a[1][1]=c[1][1]%MOD;
    a[1][2]=c[1][2]%MOD;
    a[2][1]=c[2][1]%MOD;
    a[2][2]=c[2][2]%MOD;
}

int main()
{
    in>>k;
    x[1][2]=x[2][1]=x[2][2]=1;
    y[1][1]=y[2][2]=1;
    k--;
    while(k !=0){
        if(k % 2 !=0)
            inmultire(y,x);
        k/=2;
        inmultire(x,x);
        //out<<x[1][1]<<" "<<x[1][2]<<" "<<x[2][1]<<" "<<x[2][2]<<" "<<pow<<"\n";
    }
    //calculez a^pow si pastrez rez in p
    /*while(pow != 0)
    {
        if (pow % 2 != 0)
            p *= a;
        pow /= 2;
        a *= a;
    }
    */
    out<<y[2][2];
    return 0;
}