#include <iostream>
#include <fstream>
using namespace std;
#define nmax 1000000005
#define MOD 666013
ifstream f("kfib.in");
ofstream g("kfib.out");

int n;

long long sol[2][2]= {1,0,0,1};
long long a[2][2]= {0,1,1,1};
long long x[2][2];

void calcul(long long m1[2][2],long long m2[2][2],long long m3[2][2])
{
    for (int i=0; i<2; ++i)
        for (int j=0; j<2; ++j)
        {
            m3[i][j]=0;
            for (int k=0; k<2; ++k)
            {
                m3[i][j]+=(m1[i][k]*m2[k][j])%MOD;
                m3[i][j]%=MOD;
            }
        }
}
void copie(long long din[2][2],long long in[2][2])
{
    for (int i=0; i<2; ++i)
        for (int j=0; j<2; ++j)
            in[i][j]=din[i][j];
}

int main()
{
    f>>n;
    for (int i=1; i<=n; i<<=1)
    {
        if ((n&i)>0)
        {
            calcul(a,sol,x);
            copie(x,sol);
        }
        calcul(a,a,x);
        copie(x,a);
    }
    g<<sol[1][0]%MOD;
    return 0;
}