#include <iostream>
#include <fstream>

using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

typedef long long ll;
const ll MOD=666013;

ll n;
void multiply(ll f[2][2], ll m[2][2])
{
    ll a=(f[0][0] * m[0][0]%MOD + f[0][1] * m[1][0]%MOD)%MOD;
    ll b=(f[0][0] * m[0][1]%MOD + f[0][1] * m[1][1]%MOD)%MOD;
    ll c=(f[1][0] * m[0][0]%MOD + f[1][1] * m[1][0]%MOD)%MOD;
    ll d=(f[1][0] * m[0][1]%MOD + f[1][1] * m[1][1]%MOD)%MOD;

    f[0][0]=a;
    f[0][1]=b;
    f[1][0]=c;
    f[1][1]=d;
}
void powf(ll F[2][2], ll n)
{
    if(n == 0 || n == 1)
       return;
    ll M[2][2] = {{1, 1}, {1, 0}};

    powf(F, n / 2);
    multiply(F, F);

    if (n % 2 != 0)
        multiply(F, M);
}
ll get_fib(ll n){
    if (n==0)
        return 0;
    ll fb[2][2]={{1, 1}, {1, 0}};
    powf(fb, n-1);
    return fb[0][0];
}

int main()
{
    fin>>n;
    fout<<get_fib(n);
    return 0;
}