#include <fstream>
#include <iostream>

using namespace std;

ifstream f ("kfib.in");
ofstream g ("kfib.out");

const int n = 2;
const int MOD = 666013;

struct Mat {
    int mat[2][2];
};

const Mat nullMat = {
    {
     {1, 0},
     { 0, 1}}
};

const Mat initMat = {
    {{0, 1},
     {1, 1}}
};


Mat prod(Mat p, Mat a){
    Mat aux;
    for(int i=0; i<n; i++)
        for(int k=0; k<n; k++){
            
            aux.mat[i][k] = 0;
            for(int j=0; j<n; j++)
                aux.mat[i][k] += (long long)p.mat[i][j] * a.mat[j][k]%MOD;
                aux.mat[i][k] %= MOD;
                
        }
        
    return aux;
            
}

Mat exponentiere(Mat p, int pwr){
    if(pwr == 0)
        return nullMat;
    if(pwr % 2 == 0)
        return exponentiere(prod(p, p), pwr/2);
    return prod(p, exponentiere(prod(p, p), pwr/2));
}

int main()
{
    int k;
    f>>k;
  
    g << exponentiere(initMat, k).mat[0][1] << '\n';

    return 0;
}