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

long long a[2][2] = {{0,1},{1,1}};

long long rez[2][2] = {{1,0},{0,1}};

inline void multiply(long long (&a)[2][2],long long b[2][2]) {

    int r1 = ((a)[0][0]*b[0][0]+(a)[0][1]*b[1][0]) % mod;
    int r2 = ((a)[0][0]*b[0][1]+(a)[0][1]*b[1][1]) % mod;
    int r3 = ((a)[1][0]*b[0][0]+(a)[1][1]*b[1][0]) % mod;
    int r4 = ((a)[1][0]*b[0][1]+(a)[1][1]*b[1][1]) % mod;

    (a)[0][0] = r1;
    (a)[0][1] = r2;
    (a)[1][0] = r3;
    (a)[1][1] = r4;


}


int main() {

    fstream f("kfib.in",ios::in);
    fstream g("kfib.out",ios::out);



    long p;
    f >> p;
    p--;


   while( p != 0) {

        if( p%2 == 1 ) {
            p--;
            multiply(rez,a);

        }

        multiply(a,a);
        p = p/2;



    }

    g<< rez[1][1];
}