#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000003;
int p[61];
int ksm(int x,int n)
{
	if(n==1) return x%mod;
	if(n&1) return x*ksm(x*x%mod,n/2)%mod;
	return ksm(x*x%mod,n/2)%mod;
}
int solve(int n)
{
	//printf("<%lld>\n",n);
	if(n<=2) return 0;
	int ans=0;
	int i=0;
	while((1LL<<(i+1))<=n) i++;
	int d=1LL<<i;
	ans=ans+p[i];
	int k=n-d;
	if(k==0) return ans;
	ans=(ans+solve(k)*2)%mod+ksm(2,mod-2)*(d-1+d-1-k+1)%mod*k%mod+mod;
	return ans%mod;
}
signed main()
{
	p[2]=1;
	int c=2;
	for(int i=3;i<=60;i++)
	{ 
		c=c*2;
		c=c%mod;
		p[i]=p[i-1]*3+(c-1)*c%mod*ksm(2,mod-2)%mod;
		p[i]=p[i]%mod;
	}
	int n;
	scanf("%lld",&n);
	int ans;
	ans=solve(n);
	ans=ans%mod;
	printf("%lld",ans);
	return 0;
} 

rt
思路是找最大的分形三角形然后再处理下面等差数列的偶数+两个小三角形