#include<fstream>
#include <cstring>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

int N,i,MAT[3][3],SOL[3][3];
const int mod=666013;

inline void inmult(int A[][3], int B[][3], int C[][3])
{
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
        {
            C[i][j]=(C[i][j]+1ll*A[i][k]*B[k][j])%mod;
        }
}

inline void fastpow(int P, int M[][3])
{
    int C[3][3],AUX[3][3];
    memcpy(C,MAT, sizeof(MAT));
    M[0][0]=M[1][1]=1;
    for(int i=0; (1<<i)<=N;i++)
    {
        if (P & (1 << i)) {
			memset(AUX, 0, sizeof(AUX));
			inmult(M, C, AUX);
			memcpy(M, AUX, sizeof(AUX));
		}
		memset(AUX, 0, sizeof(AUX));
		inmult(C, C, AUX);
		memcpy(C, AUX, sizeof(C));
	}
}
int main()
{
    fin>>N;
    fin.close();
    MAT[0][0] = 0; MAT[0][1] = 1; MAT[1][0] = 1; MAT[1][1] = 1;
    fastpow(N-1, SOL);
    fout<<SOL[1][1];
    fout.close();
    return 0;
}