#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");
int k;


inline void mult(int a[3][3], int b[3][3])
{
    int c[3][3];
    c[1][1]=((long long)a[1][1]*b[1][1]+(long long)a[1][2]*b[2][1])%mod;
    c[1][2]=((long long)a[1][1]*b[1][2]+(long long)a[1][2]*b[2][2])%mod;
    c[2][1]=((long long)a[2][1]*b[1][1]+(long long)a[2][2]*b[2][1])%mod;
    c[2][2]=((long long)a[2][1]*b[1][2]+(long long)a[2][2]*b[2][2])%mod;

    a[1][1]=c[1][1]%mod;
    a[1][2]=c[1][2]%mod;
    a[2][1]=c[2][1]%mod;
    a[2][2]=c[2][2]%mod;
}

int mat[3][3],sol[3][3];


inline int lgpow (int A[3][3], int P)
{
    sol[1][1] = 1;
    sol[1][2] = 0;
    sol[2][1] = 0;
    sol[2][2] = 1;

    for ( ; P; P >>= 1){
        if (P & 1)
            mult (sol, A);

        mult (A, A);
    }

    return sol[1][2] % mod;
}

int main()
{
    in>>k;
  mat[1][1]=0;
  mat[1][2]=1;
  mat[2][1]=1;
  mat[2][2]=1;

if(k<3)
{
    out<<1;
    return 0;
}

out<<lgpow(mat,k);



    return 0;
}