#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

#define MOD 666013

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

void matrMultiply(long long a[2][2], long long b[2][2]){
    long long c[2][2] = {0};
    for(int i=0;i<2;++i){
        for(int j=0;j<2;++j){
            for(int k=0;k<2;++k){
                c[i][j] = (c[i][j] + (1LL * a[i][k] * b[k][j]) % MOD) % MOD;
            }
        }
    }
    memcpy(a,c,sizeof(c));
}

void power(long long pow, long long sol[2][2], const long long mat[2][2]){
    sol[0][0] = sol[1][1] = 1;
    sol[0][1] = sol[1][0] = 0;
    long long v[2][2];
    memcpy(v,mat,sizeof(v));
    while(pow){
        if(pow%2!=0){
            matrMultiply(sol,v);
            pow--;
        }
        else{
            matrMultiply(v,v);
            pow/=2;
        }
    }
}



int main()
{
    long long k = 0;
    f>>k;
    if (k == 0) {
        g << 0;
        return 0;
    }

    long long fibMat[2][2] = {{1, 1}, {1, 0}};
    long long res[2][2] = {0};
    power(k-1, res, fibMat);

    g<<res[0][0];

    f.close();
    g.close();
    return 0;
}
/*
|Fk-1   Fk  |
|Fk     Fk+1|
*/