#include<stdio.h>
long j,j1,j2,j3,j4,j5,j6,j7,j8,j9,aa,a[100005],x[100005],n,f,p;
int main()
{
	freopen("subsir100.in","r",stdin);
	freopen("subsir100.out","w",stdout);
	scanf("%ld",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%ld",&aa);
		f=1;
		for(j=1;j<a[0];++j)if(a[j]==aa){++x[j];f=0;break;}
		if(f)a[++a[0]]=aa,x[a[0]]=1;
	}
	for(i=1;i<=a[0];++i)
	{if(i==1)
		for(j=1;j<=a[0];++j)
			p=(p+a[j])%1000003;
	if(i==2)
		for(j=1;j<=a[0];++j)
			for(j1=j+1;j1<=a[0];++j1)
			   p=(p+(a[j]*a[j1])%1000003)%1000003;
	if(i==3)
		for(j=1;j<=a[0];++j)
            for(j1=j+1;j1<=a[0];++j1)
			    for(j2=j1+1;j2<=a[0];++j2)
			        p=(p+(((a[j]*a[j1])%1000003)*a[j2])%1000003)%1000003;
	if(i==4)
		for(j=1;j<=a[0];++j)
            for(j1=j+1;j1<=a[0];++j1)
			    for(j2=j1+1;j2<=a[0];++j2)
					for(j3=j2+1;j3<=a[0];++j3)
			            p=(p+(((((a[j]*a[j1])%1000003)*a[j2])%1000003)*a[j3])%1000003)%1000003;
	if(i==5)
		for(j=1;j<=a[0];++j)
            for(j1=j+1;j1<=a[0];++j1)
			    for(j2=j1+1;j2<=a[0];++j2)
					for(j3=j2+1;j3<=a[0];++j3)
						for(j4=j3+1;j4<=a[0];++j4)
			                p=(p+(((((((a[j]*a[j1])%1000003)*a[j2])%1000003)*a[j3])%1000003)*a[j4])%1000003)%1000003;
	if(i==6)
		for(j=1;j<=a[0];++j)
            for(j1=j+1;j1<=a[0];++j1)
			    for(j2=j1+1;j2<=a[0];++j2)
					for(j3=j2+1;j3<=a[0];++j3)
						for(j4=j3+1;j4<=a[0];++j4)
							for(j5=j4+1;j5<=a[0];++j5)
			                    p=(p+(((((((((a[j]*a[j1])%1000003)*a[j2])%1000003)*a[j3])%1000003)*a[j4])%1000003)*a[j5])%1000003)%1000003;
	/*if(i==7)
		for(j=1;j<=a[0];++j)
            for(j1=j+1;j1<=a[0];++j1)
			    for(j2=j1+1;j2<=a[0];++j2)
					for(j3=j2+1;j3<=a[0];++j3)
						for(j4=j3+1;j4<=a[0];++j4)
							for(j5=j4+1;j5<=a[0];++j5)
								for(j6=j5+1;j6<=a[0];++j6)
			                        p+=(a[j]*a[j1]*a[j2]*a[j3]*a[j4]*a[j5]*a[j6]);
	if(i==8)
		for(j=1;j<=a[0];++j)
            for(j1=j+1;j1<=a[0];++j1)
			    for(j2=j1+1;j2<=a[0];++j2)
					for(j3=j2+1;j3<=a[0];++j3)
						for(j4=j3+1;j4<=a[0];++j4)
							for(j5=j4+1;j5<=a[0];++j5)
								for(j6=j5+1;j6<=a[0];++j6)
									for(j7=j6+1;j7<=a[0];++j7)
			                            p+=(a[j]*a[j1]*a[j2]*a[j3]*a[j4]*a[j5]*a[j6]*a[j7]);
	if(i==9)
		for(j=1;j<=a[0];++j)
            for(j1=j+1;j1<=a[0];++j1)
			    for(j2=j1+1;j2<=a[0];++j2)
					for(j3=j2+1;j3<=a[0];++j3)
						for(j4=j3+1;j4<=a[0];++j4)
							for(j5=j4+1;j5<=a[0];++j5)
								for(j6=j5+1;j6<=a[0];++j6)
									for(j7=j6+1;j7<=a[0];++j7)
										for(j8=j7+1;j8<=a[0];++j8)
			                                p+=(a[j]*a[j1]*a[j2]*a[j3]*a[j4]*a[j5]*a[j6]*a[j7]*a[j8]);
	if(i==10)
		for(j=1;j<=a[0];++j)
            for(j1=j+1;j1<=a[0];++j1)
			    for(j2=j1+1;j2<=a[0];++j2)
					for(j3=j2+1;j3<=a[0];++j3)
						for(j4=j3+1;j4<=a[0];++j4)
							for(j5=j4+1;j5<=a[0];++j5)
								for(j6=j5+1;j6<=a[0];++j6)
									for(j7=j6+1;j7<=a[0];++j7)
										for(j8=j7+1;j8<=a[0];++j8)
											for(j9=j8+1;j9<=a[0];++j9)
			                                    p+=(a[j]*a[j1]*a[j2]*a[j3]*a[j4]*a[j5]*a[j6]*a[j7]*a[j8]*a[j9]);*/
	}
	printf("%ld\n",p)
	return 0;
}