#include <cstdio>
using namespace std;

int k,c[30];

void b2(int x)
{
    k=0;
    while(x!=0)
    {
        c[k++]=x%2;
        x=x/2;
    }
}

void matputlg(long long &x,long long &y,long long &z,long long &t)
{
    long long x1,y1,z1,t1,p,q,r,s;
    for(int i=k-1;i>=0;--i)
    {
        x1=(x%666013*(x%666013)%666013+y%666013*(z%666013)%666013)%666013;
        y1=(x%666013*(y%666013)%666013+y%666013*(t%666013)%666013)%666013;
        z1=(z%666013*(x%666013)%666013+t%666013*(z%666013)%666013)%666013;
        t1=(z%666013*(y%666013)%666013+t%666013*(t%666013)%666013)%666013;
        if(c[i]==1)
        {
            p=x1;
            q=y1;
            r=z1;
            s=t1;
            x1=(p*1+q*1)%666013;
            y1=(p*1+q*0)%666013;
            z1=(r*1+s*1)%666013;
            t1=(r*1+s*0)%666013;
        }
        x=x1;
        y=y1;
        z=z1;
        t=t1;
    }
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    long long x=1,y=0,z=0,t=1;
    scanf("%d",&k);
    b2(k-1);
    matputlg(x,y,z,t);
    printf("%d",x);
    return 0;
}