#include <fstream>
#define MOD 666013
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
long long mat[3][3];
long long cmat[3][3];
long long mat1[3][3];
void patratmat()
{
    cmat[1][1]=mat[1][1];
    cmat[1][2]=mat[1][2];
    cmat[2][1]=mat[2][1];
    cmat[2][2]=mat[2][2];
    mat[1][1]=cmat[1][1]*cmat[1][1]+cmat[1][2]*cmat[2][1];
    mat[1][2]=cmat[1][1]*cmat[1][2]+cmat[1][2]*cmat[2][2];
    mat[2][1]=cmat[2][1]*cmat[1][1]+cmat[2][2]*cmat[2][1];
    mat[2][2]=cmat[2][1]*cmat[1][2]+cmat[2][2]*cmat[2][2];
    mat[1][1]%=MOD;
    mat[1][2]%=MOD;
    mat[2][1]%=MOD;
    mat[2][2]%=MOD;
}
void inmulmat()
{
    cmat[1][1]=mat1[1][1];
    cmat[1][2]=mat1[1][2];
    cmat[2][1]=mat1[2][1];
    cmat[2][2]=mat1[2][2];
    mat1[1][1]=cmat[1][1]*mat[1][1]+cmat[1][2]*mat[2][1];
    mat1[1][2]=cmat[1][1]*mat[1][2]+cmat[1][2]*mat[2][2];
    mat1[2][1]=cmat[2][1]*mat[1][1]+cmat[2][2]*mat[2][1];
    mat1[2][2]=cmat[2][1]*mat[1][2]+cmat[2][2]*mat[2][2];
    mat1[1][1]%=MOD;
    mat1[1][2]%=MOD;
    mat1[2][1]%=MOD;
    mat1[2][2]%=MOD;
}
int main()
{
    mat1[1][1]=1;
    mat1[1][2]=1;
    mat1[2][1]=1;
    mat1[2][2]=0;
    ///
    mat[1][1]=1;
    mat[1][2]=1;
    mat[2][1]=1;
    mat[2][2]=0;
    long long n;
    cin>>n;
    n--;
    while(n>0)
    {
        if(n%2==1)
        {
            inmulmat();
            n--;
        }
        else
        {
            patratmat();
            n/=2;
        }
    }
    cout<<mat1[2][1]%MOD;
    return 0;
}