#include <fstream>
using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

#define MOD 666013

long long k;

struct mat2x2{
                long long a, b,
                          c, d;
                mat2x2(long long x=0, long long y=0, long long z=0, long long t=0);
                mat2x2 operator *(mat2x2 x);
             };

mat2x2::mat2x2(long long x, long long y, long long z, long long t)
{
    a=x, b=y, c=z, d=t;
}

mat2x2 mat2x2::operator*(mat2x2 x)
{
    mat2x2 y;
    y.a=(a*x.a+b*x.c)%MOD;
    y.b=(a*x.b+b*x.d)%MOD;
    y.c=(c*x.a+d*x.c)%MOD;
    y.d=(c*x.b+d*x.d)%MOD;
    return y;
}

mat2x2 power(mat2x2 x, long long y)
{
    if(y==1) return x;
    else
    {
        if(y&1) return power(x*x, y/2)*x;
        else return power(x*x, y/2);
    }
}


int main()
{
    mat2x2 x(0, 1, 1, 1);
    cin>>k;
    if(k==0) cout<<0;
    else if(k==1) cout<<1;
    else
    {
        mat2x2 y=power(x, k-1);
        int f1=0, f2=1, a, b;
        a=(f1*y.a+f2*y.b)%MOD;
        b=(f1*y.c+f2*y.d)%MOD;
        cout<<b<<" ";
    }
    return 0;
}