#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

const int m = 666013;
int i, p;
long long MAT[3][3], SOL[3][3];

void mult(long long A[][3], long long B[][3], long long C[][3])
{
    int j, k;
    for(j=0; j<2; j++)
        for(k=0; k<2; k++)
            C[j][k] = ((A[j][0] * B[0][k]) % m + (A[j][1] * B[k][1]) % m) % m;
}

int main()
{
    long long AUX[3][3];
    fin >> p;
    MAT[0][1] = MAT[1][0] = MAT[1][1] = 1;
    SOL[0][0] = SOL[1][1] = 1;
    p--;
    for(i=0; (1<<i)<=p; i++)
    {
        if(p & (1<<i))
        {
            memset(AUX, 0, sizeof(AUX));
            mult(SOL, MAT, AUX);
            memcpy(SOL, AUX, sizeof(AUX));
        }
        memset(AUX, 0, sizeof(AUX));
        mult(MAT, MAT, AUX);
        memcpy(MAT, AUX, sizeof(AUX));
    }
    fout<<SOL[1][1];
    return 0;
}