#include <fstream>

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


long long v[3][3],s[3][3];


void inmultire(int k)
{
    if(k>1)
    {
        if(k%2==0)
        {
            inmultire(k/2);
            s[1][1]=v[1][1]*v[1][1]%666013+v[1][2]*v[2][1]%666013;
            s[1][1]%=666013;
            s[1][2]=v[1][1]*v[1][2]%666013+v[1][2]*v[2][2]%666013;
            s[1][2]%=666013;
            s[2][1]=v[1][1]*v[2][1]%666013+v[2][2]*v[2][1]%666013;
            s[2][1]%=666013;
            s[2][2]=v[2][1]*v[1][2]%666013+v[2][2]*v[2][2]%666013;
            s[2][2]%=666013;
            for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                v[i][j]=s[i][j];
        }
        else
        {
            inmultire(k-1);
            s[1][1]=v[1][1]+v[1][2];
            s[1][1]%=666013;
            s[1][2]=v[1][1];
            s[1][2]%=666013;
            s[2][1]=v[2][1]+v[2][2];
            s[2][1]%=666013;
            s[2][2]=v[2][1];
            s[2][2]%=666013;
            for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                v[i][j]=s[i][j];
        }
    }
    else
    {
        v[1][1]=1;
        v[1][2]=1;
        v[2][1]=1;
        v[2][2]=0;
    }
}


int main()
{
    int k;
    fin>>k;
    inmultire(k-2);
    fout<<v[1][1]+v[2][1];
    return 0;
}