#include <fstream>

const int MOD=666013;

using namespace std;

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

long long a[2][2],ans[1][2];


void multiplyansa()
{
    long long aux[1][2];
    aux[0][0]=1LL*(ans[0][0]*a[0][0]+ans[0][1]*a[1][0])%MOD;
    aux[0][1]=1LL*(ans[0][0]*a[0][1]+ans[0][1]*a[1][1])%MOD;
    ans[0][0]=aux[0][0];
    ans[0][1]=aux[0][1];
}
void multiplyaa()
{
    long long aux[2][2];
    aux[0][0]=1LL*(a[0][0]*a[0][0]+a[0][1]*a[1][0])%MOD;
    aux[0][1]=1LL*(a[0][0]*a[0][1]+a[0][1]*a[1][1])%MOD;
    aux[1][0]=1LL*(a[1][0]*a[0][0]+a[1][1]*a[1][0])%MOD;
    aux[1][1]=1LL*(a[1][0]*a[0][1]+a[1][1]*a[1][1])%MOD;
    for(int i=0; i<=1; ++i)
        for(int j=0; j<=1; ++j)
            a[i][j]=aux[i][j];
}

void atothekth(int k)
{
    int p=1;
    while(k>=p) {
        if(k&p)
            multiplyansa();
        multiplyaa();
        p=p<<1;
    }
}

int main()
{
    int k;
    cin>>k;
    k--;
    ans[0][1]=1;
    a[0][1]=a[1][0]=a[1][1]=1;
    atothekth(k);
    cout<<ans[0][1]<<'\n';
    return 0;
}