#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;
}