#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];

    for(int i = 1; i <= 2; i++)
        for(int j = 1; j <=2; j++)
        {
            c[i][j] = 0;
            for(int k = 1; k <=2; k++)
                c[i][j] += (long long)a[i][k] * b[k][j];

            c[i][j] %= MOD;
        }

    for(int i = 1; i <= 2; i++)
        for(int j = 1; j <= 2; j++)
            a[i][j] = c[i][j];
    /*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;
}