#include <fstream>
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

long long int rez[3][3],aux[3][3],b[3][3],n,mod=666013;


void laput(int k)
{
    while(k)                           // 1 2
    {                                  // 3 4
        if(k%2==1)
        {
            k--;
            aux[1][1]=rez[1][1]*b[1][1]+rez[1][2]*b[2][1]; aux[1][1]%=mod;
            aux[1][2]=rez[1][1]*b[1][2]+rez[1][2]*b[2][2]; aux[1][2]%=mod;
            aux[2][1]=rez[2][1]*b[1][1]+rez[2][2]*b[2][1]; aux[2][1]%=mod;
            aux[2][2]=rez[2][1]*b[1][2]+rez[2][2]*b[2][2]; aux[2][2]%=mod;
            rez[1][1]=aux[1][1];
            rez[1][2]=aux[1][2];
            rez[2][1]=aux[2][1];
            rez[2][2]=aux[2][2];
        }
        k/=2;
            aux[1][1]=b[1][1]*b[1][1]+b[1][2]*b[2][1]; aux[1][1]%=mod;
            aux[1][2]=b[1][1]*b[1][2]+b[1][2]*b[2][2]; aux[1][2]%=mod;
            aux[2][1]=b[2][1]*b[1][1]+b[2][2]*b[2][1]; aux[2][1]%=mod;
            aux[2][2]=b[2][1]*b[1][2]+b[2][2]*b[2][2]; aux[2][2]%=mod;
            b[1][1]=aux[1][1];
            b[1][2]=aux[1][2];
            b[2][1]=aux[2][1];
            b[2][2]=aux[2][2];

    }
}


int main()
{
    fin>>n;
    b[1][1]=0; b[1][2]=b[2][1]=b[2][2]=1; rez[1][1]=rez[2][2]=1;
    laput(n-1);

    fout<<rez[2][2];
    return 0;
}