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

struct matrix
{
    long long int m[2][2];
    void operator *= (const matrix &a)
    {
        int i,j,k;
        matrix c;
        for(i=0; i<2; ++i)
            for(j=0; j<2; ++j)
            {
                c.m[i][j]=0;
                for(k=0; k<2; ++k)
                    c.m[i][j]+=m[k][j]*a.m[i][k];
                c.m[i][j]%=mod;
            }
        for(i=0; i<2; ++i)
            for(j=0; j<2; ++j)
                m[i][j]=c.m[i][j];
    }
} r= {0,1,1,1},t= {1,0,0,1};


int main()
{

    int n;
    f>>n;
    for (int s=0; 1<<s<=n; ++s)
    {
        if (n&(1<<s))
            t*=r;
        r*=r;
    }
    g<<t.m[0][1];



    return 0;
}