#include <bits/stdc++.h>

using namespace std;

const int MOD=666013;

int v[2][2]={
    {1, 1},
    {1, 0}
};

int q[2][1]={{1}, {0}};

void multiplyav(){
    int a,b,c,d,x,y;
    a=v[0][0];
    b=v[0][1];
    c=v[1][0];
    d=v[1][1];
    x=q[0][0];
    y=q[1][0];
    q[0][0]=(1LL*a*x+1LL*b*y)%MOD;
    q[1][0]=(1LL*c*x+1LL*d*y)%MOD;
}

void multiplyvv(){
    int c[2][2]={{0,0}, {0,0}};
    for (int i=0;i<2;i++){
        for (int j=0;j<2;j++){
            for (int k=0;k<2;k++){
                c[i][j]=c[i][j]+(1LL*v[i][k]*v[k][j])%MOD;
                if (c[i][j]>MOD){
                    c[i][j]-=MOD;
                }
            }
        }
    }
    for (int i=0;i<2;i++){
        for (int j=0;j<2;j++){
            v[i][j]=c[i][j];
        }
    }
}

int lgpow(int b){
    while (b){
        if (b&1){
            multiplyav();
        }
        multiplyvv();
        b>>=1;
    }
    return q[1][0];
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int k;
    cin>>k;
    cout<<lgpow(k);
    return 0;
}