#include <iostream>
#include <tuple>
#define int long long
#define fin cin
#define fout cout

using namespace std;


const int MOD=666013;
int n;
tuple <int,int,int,int> sol;

tuple <int,int,int,int> inmultire(int a, int b, int c, int d, int e,int f, int g,int h)
{
    return make_tuple((a*e+b*g)%MOD,(a*f+b*h)%MOD,(c*e+d*g)%MOD,(c*f+d*h)%MOD);
}

tuple <int,int,int,int> putere(int p)
{
    if (p==1)
        return {0,1,1,1};

    if (p%2==1)
    {
        tuple <int,int,int,int> b=putere(p-1);
        return inmultire(0,1,1,1,get<0>(b),get<1>(b),get<2>(b),get<3>(b));
    }

    tuple <int,int,int,int> b=putere(p>>1);
    return inmultire(get<0>(b),get<1>(b),get<2>(b),get<3>(b),get<0>(b),get<1>(b),get<2>(b),get<3>(b));
}

signed main()
{
    fin>>n;

    if (n==0)
        fout<<0;
    else
    if (n<=2)
        fout<<1;
    else
    {
        sol=putere(n-2);
        fout<<(get<1>(sol)+get<3>(sol))%MOD;
    }
    return 0;
}