#include <bits/stdc++.h>

using namespace std;

const int m=2,mod=666013;

struct matrice
{
    int v[m][m];
    matrice operator *(matrice aux)
    {
        matrice b;
        b.nula();
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++)
                for(int k=0;k<m;k++)
                    b.v[i][j]=(b.v[i][j]+1LL*v[i][k]*aux.v[k][j])%mod;
        return b;
    }
    void nula()
    {
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++) v[i][j]=0;
    }
    void unitate()
    {
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++) v[i][j]=(i==j);
    }
};

matrice rid_put(matrice a,int b)
{
    matrice sol;
    sol.unitate();
    for(int i=1;i<=b;i<<=1)
    {
        if(b&i) sol=sol*a;
        a=a*a;
    }
    return sol;
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int k;
    scanf("%d",&k);
    matrice a;
    a.v[0][0]=0;
    a.v[0][1]=a.v[1][0]=a.v[1][1]=1;
    if(k==0) {printf("0");return 0;}
    a=rid_put(a,k-1);
    printf("%d",a.v[1][1]);
    return 0;
}