#include <fstream>
#define mod 666013
using namespace std;
ifstream fi("kfib.in");
ofstream fo("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[i][k]*a.m[k][j];
                    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;
    fi>>n;
    for(int s=0; 1<<s<=n; ++s)
    {
        if(n&(1<<s))
            t*=r;
        r*=r;
    }
    fo<<t.m[0][1];
    fi.close();
    fo.close();
}