#include <iostream>

using namespace std;

const int MOD = 666013;

struct mat{
    int a11, a12, a21, a22;
};

mat inmultire(mat a, mat b)
{
    mat rez;
    rez.a11 = ((a.a11 * b.a11) % MOD + (a.a12 * b.a21) % MOD) % MOD;
    rez.a12 = ((a.a11 * b.a12) % MOD + (a.a12 * b.a22) % MOD) % MOD;
    rez.a21 = ((a.a21 * b.a11) % MOD + (a.a22 * b.a21) % MOD) % MOD;
    rez.a22 = ((a.a21 * b.a12) % MOD + (a.a22 * b.a22) % MOD) % MOD;
    return rez;
}

mat exp(mat a, int n)
{
    if(n == 0) {return {1, 0, 0, 1};}
    if(n % 2) return inmultire(a, exp(a, n - 1));
    mat aux = exp(a, n / 2);
    return (inmultire(aux, aux));
}

int main()
{   
    int n; cin >> n;
    mat fibo = exp({1, 1, 1, 0}, n - 1);
    cout << fibo.a11;
    // mat test = exp({1, 1, 1, 1}, n);
    // cout << test.a11 << ' ' << test.a12 << '\n' << test.a21 << ' ' << test.a22;
}