#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

long long m[2][2], a[2][2], z[2][2], v[2], v1[2];

int putere(int k){
//in matricea m vom avea in final rezultatul
//pentru inceput o initzializam cu matricea I (identitate) - elem. neutru la
//inmultzirea matricelor
    m[0][0]=1;m[1][0]=0;
    m[1][0]=0;m[1][1]=1;
    while(k){
        if(k % 2 != 0){//facem inmultzirea matriceala M=M*A
            z[0][0] = (m[0][0]* a[0][0] + m[0][1] * a[1][0])%666013;
            z[0][1] = (m[0][0] * a[0][1] + m[0][1] * a[1][1])%666013;
            z[1][0] = (m[1][0]* a[0][0] + m[1][1] * a[1][0])%666013;
            z[1][1] = (m[1][0] * a[0][1] + m[1][1] * a[1][1])%666013;
            m[0][0] = z[0][0];
            m[0][1] = z[0][1];
            m[1][0] = z[1][0];
            m[1][1] = z[1][1];
            k--;
        } else{//facem inmultzirea matriceala A=A*A
            z[0][0] = (a[0][0]* a[0][0] + a[0][1] * a[1][0])%666013;
            z[0][1] = (a[0][0] * a[0][1] + a[0][1] * a[1][1])%666013;
            z[1][0] = (a[1][0]* a[0][0] + a[1][1] * a[1][0])%666013;
            z[1][1] = (a[1][0] * a[0][1] + a[1][1] * a[1][1])%666013;
            a[0][0] = z[0][0];
            a[0][1] = z[0][1];
            a[1][0] = z[1][0];
            a[1][1] = z[1][1];
            k /= 2;
        }
    }
    return m[1][0];
}

int main()
{
    long long k;
    a[0][0] = 0;
    a[0][1] = 1;
    a[1][0] = 1;
    a[1][1] = 1;
    fin >> k;
    fout<<putere(k);
    return 0;
}