#include <fstream>
using namespace std;
#define MOD 666013
int k;
long long a[2][2], rez[2][2];
ifstream fin("kfib.in");
ofstream fout("kfib.out");
void mulmat(long long x[][2], long long y[][2]);
int putere(int n);
int main()
{
    fin>>k;
    putere(k);
    fout<<rez[0][1]<<'\n';
    return 0;
}
void mulmat(long long x[][2], long long y[][2]){
    long long a00, a01, a10, a11;
    a00 = (x[0][0]*y[0][0] + x[0][1]*y[1][0])%MOD;
    a01 = (x[0][0]*y[0][1] + x[0][1]*y[1][1])%MOD;
    a10 = (x[1][0]*y[0][0] + x[1][1]*y[1][0])%MOD;
    a11 = (x[1][0]*y[0][1] + x[1][1]*y[1][1])%MOD;
    x[0][0] = a00; x[0][1] = a01; x[1][0] = a10;x[1][1] = a11;
}
int putere(int n){
    a[0][1] = a[1][0] = a[1][1] = rez[0][0] = rez[1][1] = 1;
    for(;n;n>>=1){
        if(n&1) mulmat(rez, a);
        mulmat(a, a);
    }
}