#include<cstdio>
#define mod 666013
using namespace std;
long long a11,a12,a21,a22,x11,x12,x21,x22,m11,m12,m21,m22;
int k;
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d", &k);
    k-=2;
    a11=x11=0;
    a12=x12=1;
    a21=x21=1;
    a22=x22=1;
    for(;k;k/=2)
    {
        if(k%2)
        {
            m11=((x11*a11)%mod+(x12*a21)%mod)%mod;
            m12=((x11*a12)%mod+(x12*a22)%mod)%mod;
            m21=((x21*a11)%mod+(x22*a21)%mod)%mod;
            m22=((x21*a12)%mod+(x22*a22)%mod)%mod;
            x11=m11;
            x12=m12;
            x21=m21;
            x22=m22;
        }
        m11=((a11*a11)%mod+(a12*a21)%mod)%mod;
        m12=((a11*a12)%mod+(a12*a22)%mod)%mod;
        m21=((a21*a11)%mod+(a22*a21)%mod)%mod;
        m22=((a21*a12)%mod+(a22*a22)%mod)%mod;
        a11=m11;
        a12=m12;
        a21=m21;
        a22=m22;
    }
    printf("%lld ", x22);
    return 0;
}