#include <iostream>
#include <fstream>
#define Mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long M[2][2],Rez[2][2],I3[2][2];
long long k;
void LogPow(long long exp)
{
    while(exp)
    {
        Rez[0][0]=Rez[1][1]=Rez[1][0]=Rez[0][1]=0;
        if(exp%2)
        {

            for(int i=0; i<2; i++)
                for(int j=0; j<2; j++)
                    for(int k=0; k<2; k++)
                        Rez[i][j]=(Rez[i][j]+(1LL*I3[i][k]*M[k][j])%Mod)%Mod;

            for(int i=0; i<2; i++)
                for(int j=0; j<2; j++)
                    I3[i][j]=Rez[i][j];

        }

        Rez[0][0]=Rez[1][1]=Rez[1][0]=Rez[0][1]=0;
        for(int i=0; i<2; i++)
            for(int j=0; j<2; j++)
                for(int k=0; k<2; k++)
                    Rez[i][j]=(Rez[i][j]+(1LL*M[i][k]*M[k][j])%Mod)%Mod;

        for(int i=0; i<2; i++)
            for(int j=0; j<2; j++)
                M[i][j]=Rez[i][j];

        exp/=2;
    }
}
int main()
{
    f>>k;

    M[0][1]=M[1][0]=M[1][1]=1;
    I3[1][1]=I3[0][0]=1;

    LogPow(k-1);

    g<<I3[1][1]%Mod;

    return 0;
}