#include <fstream>
#define ll long long
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

ll n;
ll fib[3][3], ans[3][3];
void inm(ll a[3][3], ll b[3][3])
{
    ll rez[3][3];
    rez[1][1] = rez[1][2] = rez[2][1] = rez[2][2] = 0;
    for(int i = 1; i <= 2; ++i)
        for(int k = 1; k <= 2; ++k)
            for(int j = 1; j <= 2; ++j)
            rez[i][k] = (rez[i][k] + a[i][j] * b[j][k] ) % mod;

    for(int i = 1; i <= 2; ++i)
        for(int j = 1; j <= 2; ++j)
            a[i][j] = rez[i][j];
}
void logpow(ll b)
{
    while(b)
    {
        if(b & 1)
            inm(ans, fib);
        b >>= 1;
        inm(fib,fib);
    }
}
int main()
{
    f >> n;
    fib[1][2] = ans[1][2] = 1;
    fib[2][2] = ans[2][2] = 1;
    fib[2][1] = ans[2][1] = 1;
    logpow(n);
    g << ans[1][1];
    f.close();
    g.close();
    return 0;
}