#include<fstream>
#include<map>
using namespace std;
#define ll long long
#define mod 666013
ll n;
map <ll,ll>  Fib;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

ll fib(ll n)
{
     if (n<2) return 1;
     if (Fib.find(n)!=Fib.end()) return Fib[n];
     Fib[n] = ( fib((n+1)/2)*fib(n/2) + fib((n-1)/2)*fib((n-2)/2) )%mod;
     return Fib[n];
 }

int main()
{
	cin>>n;
	if (!n) cout<<0;
	else cout<<fib(n-1);
	return 0;
}