#include <fstream>
#define MOD 666013

using namespace std;

int k;
long long A[2][2]={{0,1},{1,1}};
long long F[2][2]={{1,0},{0,1}};

void product(long long R[2][2],long long I[2][2])
{
    int aux[2][2];
    aux[0][0]=(R[0][0]*I[0][0]+R[0][1]*I[1][0])%MOD;
    aux[0][1]=(R[0][0]*I[0][1]+R[0][1]*I[1][1])%MOD;
    aux[1][0]=(R[1][0]*I[0][0]+R[1][1]*I[1][0])%MOD;
    aux[1][1]=(R[1][0]*I[1][0]+R[1][1]*I[1][1])%MOD;

    for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)
            R[i][j]=aux[i][j];
}

ifstream cin("kfib.in");
ofstream cout("kfib.out");

int main()
{

    cin>>k;

    do
    {
        if(k%2!=0)
            product(F,A);

        product(A,A);
        k/=2;
    }while(k);

    cout<<F[1][0];
}