#include<bits/stdc++.h>
#define ll long long
#define mod 666013

using namespace std;

int fib(ll n)
{
    double rad5 = sqrt(5);
    double phi=(1+rad5)/2;
    return round(pow(phi,n)/rad5);

}
int main()
{
    FILE *in = fopen("kfib.in","r");
    FILE *out = fopen("kfib.out","w");

    ll n;

    fscanf(in,"%lld",&n);
    n=(1LL*fib(n))%mod;
    fprintf(out,"%lld",n);
}