#include <cstdio>
#include <algorithm>
using namespace std;
#define MOD 666013

typedef long long ll;

ll f[2][2]={{0,1},{1,1}}; // matricea unitate
ll r[2][2]={{0,1},{1,1}}; // matricea raspuns

void produs(ll r[2][2],ll x[2][2]){
    ll a[2][2];
    a[0][0] = (r[0][0] * x[0][0]) % MOD + (r[0][1] * x[1][0]) % MOD;
    a[0][1] = (r[0][0] * x[0][1]) % MOD + (r[0][1] * x[1][1]) % MOD;
    a[1][0] = (r[1][0] * x[0][0]) % MOD + (r[1][1] * x[1][0]) % MOD;
    a[1][1] = (r[1][0] * x[0][1]) % MOD + (r[1][1] * x[1][1]) % MOD;
    for(int i=0;i<2;i++)
    for(int j=0;j<2;j++) r[i][j] = a[i][j] % MOD; // salvam rezultatul
}

void pow(int p){
    if(p>1)
    {
        pow(p/2);
        if(p%2)
        {
            produs(r,r);
            produs(r,f);
        } else
            produs(r,r);
    }
}

int main(){
    int n;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    scanf("%d",&n);

    pow(n+1);

    printf("%lld\n",r[0][0]);

    return 0;
}