#include <iostream>
#include <cmath>
#include <fstream>

using namespace std;

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

#define cin fin
#define cout fout

const int MOD = 666013;

long long n,A[3][3],B[3][3],C[3][3],D[3][3],F[3][3],k;

void Init(long long A[3][3])
{
    A[1][1]=A[1][2]=A[2][1]=1;
    A[2][2]=0;
}

void MultMat(long long A[3][3], long long B[3][3])
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            C[i][j]=A[i][j];
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            D[i][j]=B[i][j];
    A[1][1]=((1LL*C[1][1]*D[1][1])%MOD+(1LL*C[1][2]*D[2][1])%MOD)%MOD;
    A[1][2]=((1LL*C[1][1]*D[1][2])%MOD+(1LL*C[1][2]*D[2][2])%MOD)%MOD;
    A[2][1]=((1LL*C[2][1]*D[1][1])%MOD+(1LL*C[2][2]*D[2][1])%MOD)%MOD;
    A[2][2]=((1LL*C[2][1]*D[1][2])%MOD+(1LL*C[2][2]*D[2][2])%MOD)%MOD;
}

void Pow(long long A[3][3], int P)
{
    if(P==1)
        return;
    else
    {
        if(P%2==0)
        {
            Pow(A,P/2);
            MultMat(A,A);
        }
        else
        {
            Pow(A,P-1);
            MultMat(A,B);
        }
    }
}

int main()
{
    cin>>n;
    Init(A);
    Init(B);
    if(n<=3)
    {
        if(n<=2)
            cout<<1<<'\n';
        else
            cout<<2<<'\n';
    }
    else
    {
        k=n-1;
        Pow(A,k);
        cout<<A[1][1]<<'\n';
    }
}