#include <fstream>
#define MOD 666013
using namespace std;
ifstream f ("kfib.in");
ofstream g ("kfib.out");
int usu[5][5],mat[5][5],i2[5][5],n;
void exponentiere()
{
    while(n)
    {
        if(n%2)
        {
            usu[1][1]=i2[1][1]*mat[1][1]+i2[1][2]*mat[2][1];
            usu[1][2]=i2[1][1]*mat[1][2]+i2[1][2]*mat[2][2];
            usu[2][1]=i2[2][1]*mat[1][1]+i2[2][2]*mat[2][1];
            usu[2][2]=i2[2][1]*mat[1][2]+i2[2][2]*mat[2][2];
            i2[1][1]=usu[1][1]%MOD;
            i2[1][2]=usu[1][2]%MOD;
            i2[2][1]=usu[2][1]%MOD;
            i2[2][2]=usu[2][2]%MOD;
        }
        usu[1][1]=mat[1][1]*mat[1][1]+mat[1][2]*mat[2][1];
        usu[1][2]=mat[1][1]*mat[1][2]+mat[1][2]*mat[2][2];
        usu[2][1]=mat[2][1]*mat[1][1]+mat[2][2]*mat[2][1];
        usu[2][2]=mat[2][1]*mat[1][2]+mat[2][2]*mat[2][2];
        mat[1][1]=usu[1][1]%MOD;
        mat[1][2]=usu[1][2]%MOD;
        mat[2][1]=usu[2][1]%MOD;
        mat[2][2]=usu[2][2]%MOD;
        n/=2;
    }
}
int main()
{
    f>>n;
    mat[1][1]=0;
    mat[1][2]=1;
    mat[2][1]=1;
    mat[2][2]=1;
    i2[1][1]=1;
    i2[1][2]=0;
    i2[2][1]=0;
    i2[2][2]=1;
    exponentiere();
    g<<i2[2][1];
    return 0;
}