#include <fstream>
#define MODUL 666013
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");
int n;
int Zet[3][3];
int baza2[100];
int Res[3][3];
void precomp() {
    Zet[1][1] = 0;
    Zet[1][2] = 1;
    Zet[2][1] = 1;
    Zet[2][2] = 1;
    Res[1][1] = 1;
    Res[2][2] = 1;
}
void matrixProduct(int A[3][3], int B[3][3]) {
    int InterMed[3][3];
    for(int i = 1; i <= 2; i++)
     for(int j = 1; j <= 2; j++) {
         int sum = (((1LL * A[i][1] * B[1][j]) % MODUL) + ((1LL * A[i][2] * B[2][j]) % MODUL)) % MODUL;
         InterMed[i][j] = sum;
     }
     for(int i = 1; i <= 2; i++)
      for(int j = 1; j <= 2; j++) {
          Res[i][j] = InterMed[i][j];
      }
}
void descompune(int nr) {
    while(nr) {
        baza2[++baza2[0]] = nr % 2;
        nr /= 2;
    }
}
void solve(int n) {
    descompune(n - 1);
    for(int i = baza2[0]; i > 0; i--) {
        matrixProduct(Res, Res);
        if(baza2[i] == 1)
            matrixProduct(Res, Zet);
    }
    g << Res[2][2] % MODUL;
}
int main()
{
    precomp();
    f >> n;
    solve(n);
    return 0;
}