#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

const int MOD=666013;

int add(int a,int b)
{
        a+=b;
        if(a>=MOD) return a-MOD;
        if(a<0) return a+MOD;
        return a;
}

int mul(int a,int b)
{
        return a*(long long)b%MOD;
}

int sqr(int a)
{
        return mul(a,a);
}

map <int,int> fib;

int get_fib(int n)
{
        if(fib[n])
        {
                return fib[n];
        }
        int k=n/2;
        if(n%2==1)
        {
                return fib[n]=mul(get_fib(k),add(get_fib(k-1),get_fib(k+1)));
        }
        else
        {
                return fib[n]=add(sqr(get_fib(k)),sqr(get_fib(k-1)));
        }
}

int main()
{
        freopen("kfib.in","r",stdin);
        freopen("kfib.out","w",stdout);
        fib[0]=1;
        fib[1]=1;
        fib[2]=2;
        fib[3]=3;
        int e;
        cin>>e;
        cout<<get_fib(e-1)<<"\n";
        return 0;
}