#include<fstream>
#include<string.h>
#define mod 666013
#define ll long long
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");

ll n,fib[2][2],z[2][2];

void mult(ll a[2][2], ll b[2][2])
{
    ll i,j,k,c[2][2];
    memset(c,0,sizeof(c));
    for(i=0;i<2;++i)
        for(j=0;j<2;++j)
            for(k=0;k<2;++k)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
    for(i=0;i<2;++i)
        for(j=0;j<2;++j)
            a[i][j]=c[i][j];
}

void lg_pow(ll p)
{
    while(p){
        if(p%2)
            mult(fib,z);
        mult(z,z);
        p/=2;
    }
}

int main(){
    in>>n;
    z[0][1]=z[1][0]=z[1][1]=1;
    fib[0][0]=fib[1][1]=1;
    lg_pow(n);
    out<<fib[0][1];
    return 0;
}