思路是直接推公式，
得到前n行的奇数个数
若 n=2^k + 2^(k-1) + … + 2^1 + 2^0
则 个数为

num=3^k * 2^0 + 3^(k-1) * 2^1 + 3^(k-2) * 2^2 +… + 3^0 * 2^m

（m表示 项数-1）

其他点都能过，但是#1和#5给WA了QnQ

求dalao指点指点 %%%

#include<iostream>
#include<cmath>
using namespace std;
long long t,n,m,x,y,ans,c,p=1000003;
long long total,wn,ji;
long long p3[1000],p2[1000];
bool w[10000000];
void pow3(long long n){		//提前算出3^0到3^n
	long long s=1;
	for(register int i=0;i<=n;i++,s*=3){
		s%=p;
		p3[i]=s;
	}
}
void pow2(long long n){		//提前算出2^0到2^n 
	long long s=1;
	for(register int i=0;i<=n;i++,s*=2){
		s%=p;
		p2[i]=s;	
	}
}
							//扩欧 
long long exgcd(long long a,long long b,long long &x,long long &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	else{
		long long gcd=exgcd(b,a%b,x,y);
		long long t=x;
		x=y;
		y=t-a/b*y;
		return gcd;
	}
}

int main(){
	scanf("%lld",&n);
	exgcd(2,p,x,y);			//算出2在mod p下的乘法逆元 
	while(x<0) x+=p;
	total=n%p*(n+1)%p*x%p;	//算出前n行的数的个数 
	while(n>0){				//用bool数组储存n的二进制形式 
		w[wn++]=n%2;
		n/=2;
	}
	pow2(wn);				
	pow3(wn);
	t=0;
	for(register int i=wn;i>=0;i--){
		if(w[i]){
			ji=(ji+p3[i]%p*p2[t++]%p)%p;  // 奇数个数+=3^i * 2^k 
		}
	}
	ans=(total-ji)%p;		//计算偶数个数 
	while(ans<0) ans+=p;	//处理负数情况 
	printf("%lld",ans);
}