#include <iostream>
#include <fstream>

using namespace std;

const long long MOD = 666013;

void matrix_szorzas(long long a[2][2],long long b[2][2],long long c[2][2]) {

    for(int i=0; i<2; i++) {
        for(int j=0; j<2; j++) {
            c[i][j] = 0;
            for(int k=0; k<2; k++) {
                c[i][j] = (c[i][j] + a[i][k]*b[k][j]%MOD)%MOD;
            }
        }
    }
}

void hatvany(long long n[2][2], long long k, long long eredmeny[2][2]) {

    if(k==0) {
        eredmeny[0][0] = 1;
        eredmeny[0][1] = 0;
        eredmeny[1][0] = 0;
        eredmeny[1][1] = 1;
        return;
    }
    if(k%2==0) {
        long long s[2][2];
        hatvany(n, k/2, s);
        matrix_szorzas(s,s,eredmeny);
    } else {
        long long s[2][2];
        hatvany(n, k/2,s);
        long long seged[2][2];
        matrix_szorzas(s,s,seged);
        matrix_szorzas(seged,n,eredmeny);
    }

}

int main()
{
    long long fszam;
    long long alap[2][2] = { {0,1}, {1,1} };
    ifstream in("kfib.in");
    in >> fszam;
    ofstream out("kfib.out");
    long long er[2][2];
    hatvany(alap,fszam,er);
    out << er[1][0];

    return 0;
}