#include <iostream>
#include <fstream>
#define mod 666013
#define LL long long
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
LL z[2][2] = {{0, 1}, {1, 1}};
LL rez[2][2] = {{0, 1}, {1, 1}};
void inm (LL a[2][2], LL b[2][2])
{
    LL x = (a[0][0] * b[0][0] % mod + a[0][1] * b[1][0] % mod) % mod;
    LL y = (a[0][0] * b[0][1] % mod + a[0][1] * b[1][1] % mod) % mod;
    LL z = (a[1][0] * b[0][0] % mod + a[1][1] * b[1][0] % mod) % mod;
    LL t = (a[1][0] * b[0][1] % mod + a[1][1] * b[1][1] % mod) % mod;
    rez[0][0] = x;
    rez[0][1] = y;
    rez[1][0] = z;
    rez[1][1] = t;
}
void lgpow(int pow)
{
    if(pow == 1)
        return;
    if(pow % 2 == 0)
    {
        lgpow(pow / 2);
        inm(rez, rez);
    }
    else{
        lgpow(pow - 1);
        inm(z, rez);
    }
}
int k;
int main()
{
    fin >> k;
    lgpow(k - 1);
    fout << rez[1][1] % mod;
    return 0;
}