#include <fstream>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int MOD=666013;
void prodmat(int a[2][2],int b[2][2],int c[2][2])
{
    int i,j;
    for(i=0;i<=1;++i)
        for(j=0;j<=1;++j)
            {
                c[i][j]=(a[i][0]*b[0][j]+a[i][1]*b[1][j])%MOD;
            }
}
void fast_pow(int k)
{
    int i,j;
    int bb[2][2]={1,0,0,1},p[2][2]={1,1,1,0},r[2][2];
    for(;k;k=k>>1)
    {
        if(k&1)
        {
        prodmat(bb,p,r);
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
                bb[i][j]=r[i][j];
        }
        prodmat(p,p,r);
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
                p[i][j]=r[i][j];
    }
    fout<<bb[0][1];
}
int main()
{
    int k,i,j;
    fin>>k;
    fast_pow(k);
    return 0;
}