//horatiu11
# include <cstdio>
# define mod 666013
using namespace std;
int n;
int Z[2][2],Rez[2][2];
inline void mult(int X[2][2], int Y[2][2], int C[2][2])
{
    C[0][0]=(X[0][0]*Y[0][0]%mod+X[0][1]*Y[1][0]%mod)%mod;
    C[0][1]=(X[0][0]*Y[0][1]%mod+X[0][1]*Y[1][1]%mod)%mod;
    C[1][0]=(X[1][0]*Y[0][0]%mod+X[1][1]*Y[1][0]%mod)%mod;
    C[1][1]=(X[1][0]*Y[0][1]%mod+X[1][1]*Y[1][1]%mod)%mod;
}
inline void lg_pow(int A[2][2], int B[2][2], int k)
{
    if(k>0)
    {
        if(k%2)
        {
            lg_pow(A,B,k-1);
            mult(A,B,A);
        }
        else if(k%2==0)
        {
            lg_pow(A,B,k/2);
            mult(A,A,A);
        }
    }
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    Z[0][0]=0;Z[0][1]=1;Z[1][0]=1;Z[1][1]=1;
    Rez[0][0]=0;Rez[0][1]=1;Rez[1][0]=1;Rez[1][1]=1;
    lg_pow(Z,Rez,n-1);
    printf("%d",Rez[1][1]);
    return 0;
}