#include <iostream>
#include <fstream>
#define mod 666013
#define S(x, y) ((x + y) % mod)
#define P(x, y) ((1LL*x * y) % mod)
using namespace std;

int k;
typedef struct {
    int x1, x2, x3, x4;
} matrix;
matrix A, Z = {0, 1, 1, 1}, I = {1, 0, 0, 1};
matrix produs(matrix A, matrix B)
{
   matrix C = {S(P(A.x1, B.x1), P(A.x2, B.x3)), S(P(A.x1, B.x2), P(A.x2, B.x4)), S(P(A.x3, B.x1), P(A.x4, B.x3)), S(P(A.x3, B.x2), P(A.x4, B.x4))};
   return C;
}
matrix solve(matrix A, int i)
{
   if(i == 0) return I;
   if(i % 2 == 0){
      A = produs(A, A);
      return solve(A, i / 2);
   }
    else {
        I = produs(I, A);
        return solve(A, i - 1);
     }
}
int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    fin >> k;
    A = solve(Z, k - 1);
    fout << A.x4;
    return 0;
}