//horatiu11
# include <cstdio>
# define mod 666013
using namespace std;
int n;
long long Z[2][2],Rez[2][2],C[2][2];
inline void mult(long long X[2][2], long long Y[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(long long A[2][2], long long B[2][2], int k)
{
    if(k>1)
    {
        if(k%2)
        {
            lg_pow(A,B,k-1);
            mult(A,B);
            A[0][0]=C[0][0];A[0][1]=C[0][1];A[1][0]=C[1][0];A[1][1]=C[1][1];
        }
        else if(k%2==0)
        {
            lg_pow(A,B,k/2);
            mult(A,A);
            A[0][0]=C[0][0];A[0][1]=C[0][1];A[1][0]=C[1][0];A[1][1]=C[1][1];
        }
    }
}
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(Rez,Z,n);
    printf("%lld",Rez[0][1]%mod);
    return 0;
}